International Journal of Computational Geometry & Applications

We study pursuit-evasion in a polygonal environment with polygonal obstacles. In this turn based game, an evader $e$ is chased by pursuers $p_1,p_2,\dots ,p_{\ell }$. The players have full information about the environment and the location of the other players. The pursuers are allowed to coordinate their actions. On the pursuer turn, each $p_i$ can move to any point at distance at most 1 from his current location. On the evader turn, he moves similarly. The pursuers win if some pursuer becomes co-located with the evader in finite time. The evader wins if he can evade capture forever.

It is known that one pursuer can capture the evader in any simply-connected polygonal environment, and that three pursuers are always sufficient in any polygonal environment $P$ (possibly with polygonal obstacles). We contribute two new results to this field. First, we fully characterize when an environment with a single obstacle is one-pursuerwin or two-pursuer-win. Second, we give sufficient (but not necessary) conditions for an environment to have a winning strategy for two pursuers. Such environments can be swept by a leapfrog strategy in which the two cops alternately guard/increase the currently controlled area. The running time of this algorithm is $O(n\cdot h\cdot \text{diam}(P\left)\right)$ where $n$ is the number of vertices, $h$ is the number of obstacles and $\text{diam}\left(P\right))$ is the diameter of the polygonal environment $P$.

More concretely, for an environment with $n$ vertices, we describe an $O\left(n^2\right)$ algorithm that (1) determines whether the obstacles are well-separated, and if so, (2) constructs the required partition for a leapfrog strategy.

Associating the regions of a geographic subdivision with the cells of a grid is a basic operation that is used in various types of maps, like spatially ordered treemaps and Origin-Destination maps (OD maps). In these cases the regular shapes of the grid cells allow easy representation of extra information about the regions. The main challenge is to find an association that allows a user to find a region in the grid quickly. We call the representation of a set of regions as a grid a grid map.

We introduce a new approach to solve the association problem for grid maps by formulating it as a point set matching problem: Given two sets $A$ (the centroids of the regions) and $B$ (the grid centres) of $n$ points in the plane, compute an optimal one-to-one matching between $A$ and $B$. We identify three optimisation criteria that are important for grid map layout: maximise the number of adjacencies in the grid that are also adjacencies of the regions, minimise the sum of the distances between matched points, and maximise the number of pairs of points in $A$ for which the matching preserves the directional relation (SW, NW, etc.). We consider matchings that minimise the $L_1$-distance (Manhattan-distance), the ranked $L_1$-distance, and the $L_2^2$-distance, since one can expect that minimising distances implicitly helps to fulfill the other criteria.

We present algorithms to compute such matchings and perform an experimental comparison that also includes a previous method to compute a grid map. The experiments show that our more global, matching-based algorithm outperforms previous, more local approaches with respect to all three optimisation criteria.

We revisit the $L_{\infty }$ Hausdorff Voronoi diagram of clusters of points in the plane and present a simple two-pass plane sweep algorithm to construct it. This problem is motivated by applications in the semiconductor industry, in particular, critical area analysis and yield prediction in VLSI design. We show that the structural complexity of this diagram is $\mathrm{\Theta }(n+m)$, where $n$ is the number of given clusters and $m$ is a number of specially crossing clusters, called essential. Our algorithm runs in $O\left(\right(n+m\text{'}\left)\text{log}n\right)$ time and $O(n+m\text{'})$ space, where $m\text{'}$ reflects a slight superset of essential crossings, $m\le m\text{'}\le M$, and $M$ is the total number of crossing clusters. For non-crossing clusters ($M=0$) or clusters with only a small number of crossings ($M\in O\left(n\right)$) the algorithm is optimal. The latter is the case of interest in the motivating application, where $M\ll n^2$. This is achieved by augmenting the wavefront data structure of the plane sweep, and a preprocessing step, based on point dominance, which is interesting in its own right.

The far-field reflector problem is a well-known inverse problem arising in geometric optics. It consists in creating a mirror that reflects a given point light source to a prescribed target light at infinity. In this article, we study this problem under the common design constraint that the mirror is convex and is the graph of a polynomial over a given plane. We propose a method that iteratively improves the optical properties of the mirror surface while strictly fulfilling the design constraints. At each iteration, we first create an initial reflector by solving an optimal transport problem on the sphere. We then parameterize this reflector by the graph of a function over the plane. We test our algorithm with classical target lights at infinity and also show that our approach allows to create reflectors with more complex target lights.