Abstract Voronoi diagrams are defined in terms of a given system of planar bisecting curves satisfying some simple combinatorial properties. They offer a unifying framework for a wide range of concrete Voronoi instances on generalized sites and metrics. In this paper, we formulate higher-order abstract color Voronoi diagrams of a set S of n colored abstract sites, simultaneously considering all concrete instances under their umbrella. We prove that the number of vertices in the order-k abstract color Voronoi diagram is at most 4k(n-k)-2n, and present an iterative construction algorithm. The bound directly applies to a family of m disjoint simple polygons of total complexity n. For simple polygons the bound can further improve to O(min{k(n-k),(m-k)²n}). A critical ingredient of our proof is a combinatorial analysis on circular sequences of color permutations derived from the unbounded edges of these diagrams that is interesting in its own right.

Given a set $S$ of $n$ colored sites, each $s\in S$ associated with a distance-to-site function $δ_s \colon \mathbb{R}^2 \to \mathbb{R}$, we consider two distance-to-color functions for each color: one takes the minimum of $δ_s$ for sites $s\in S$ in that color and the other takes the maximum. These two sets of distance functions induce two families of higher-order Voronoi diagrams for colors in the plane, namely, the minimal and maximal order-$k$ color Voronoi diagrams, which include various well-studied Voronoi diagrams as special cases. In this paper, we derive an exact upper bound $4k(n-k)-2n$ on the total number of vertices in both the minimal and maximal order-$k$ color diagrams for a wide class of distance functions $δ_s$ that satisfy certain conditions, including the case of point sites $S$ under convex distance functions and the $L_p$ metric for any $1\leq p \leq\infty$. For the $L_1$ (or, $L_\infty$) metric, and other convex polygonal metrics, we show that the order-$k$ minimal diagram of point sites has $O(\min\{k(n-k), (n-k)^2\})$ complexity, while its maximal counterpart has $O(\min\{k(n-k), k^2\})$ complexity. To obtain these combinatorial results, we extend the Clarkson--Shor framework to colored objects, and demonstrate its application to several fundamental geometric structures, including higher-order color Voronoi diagrams, colored $j$-facets, and levels in the arrangements of piecewise linear/algebraic curves/surfaces. We also present an iterative approach to compute higher-order color Voronoi diagrams.

Given a set P of n points in the plane, the two-line center problem asks to find two lines that minimize the maximum distance from each point in P to its closer one of the two resulting lines. The currently best algorithm for the problem takes $O(n^2\log^2n)$ time by Jaromczyk and Kowaluk in 1995. In this paper, we present faster algorithms for three variants of the two-line center problem in which the orientations of the resulting lines are constrained. Specifically, our algorithms solve the problem in $O(n \log n)$ time when the orientations of both lines are fixed; in $O(n \log^3 n)$ time when the orientation of one line is fixed; and in $O(n^2 α(n) \log n)$ time when the angle between the two lines is fixed, where $α(n)$ denotes the inverse Ackermann function.

This paper studies empty squares in arbitrary orientation among a set $P$ of $n$ points in the plane. We prove that the number of empty squares with four contact pairs is between $Ω(n)$ and $O(n^2)$, and that these bounds are tight, provided $P$ is in a certain general position. A contact pair of a square is a pair of a point $p\in P$ and a side $\ell$ of the square with $p\in \ell$. The upper bound $O(n^2)$ also applies to the number of empty squares with four contact points, while we construct a point set among which there is no square of four contact points. These combinatorial results are based on new observations on the $L_\infty$ Voronoi diagram with the axes rotated and its close connection to empty squares in arbitrary orientation. We then present an algorithm that maintains a combinatorial structure of the $L_\infty$ Voronoi diagram of $P$, while the axes of the plane continuously rotates by $90$ degrees, and simultaneously reports all empty squares with four contact pairs among $P$ in an output-sensitive way within $O(s\log n)$ time and $O(n)$ space, where $s$ denotes the number of reported squares. Several new algorithmic results are also obtained: a largest empty square among $P$ and a square annulus of minimum width or minimum area that encloses $P$ over all orientations can be computed in worst-case $O(n^2 \log n)$ time.

In this paper, we study the problem of computing a minimum-width double-strip or parallelogram annulus that encloses a given set of n points in the plane. A double-strip is a closed region in the plane whose boundary consists of four parallel lines and a parallelogram annulus is a closed region between two edge-parallel parallelograms. We present several first algorithms for these problems. Among them are O(n2) and O(n3log⁡n)-time algorithms that compute a minimum-width double-strip and parallelogram annulus, respectively, when their orientations can be freely chosen.

Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of n disks in the plane. Initially, all disks have radius 0, and they grow at constant, but possibly different, speeds. Whenever two disks touch, the one with the higher index disappears. The goal is to determine the elimination order, i.e., the order in which the disks disappear. We provide the first general subquadratic algorithm for this problem. Our solution extends to other shapes (e.g., rectangles), and it works in any fixed dimension. We also describe an alternative algorithm that is based on quadtrees. Its running time is O ( n ( log ⁡ n + min ⁡ { log ⁡ Δ , log ⁡ Φ } ) ) , where Δ is the ratio of the fastest and the slowest growth rate and Φ is the ratio of the largest and the smallest distance between two disk centers. This improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EuroCG 2017]. Finally, we give an Ω ( n log ⁡ n ) lower bound, showing that our quadtree algorithms are almost tight.

We prove a generalization of Pál's 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360° inside Q. We also prove a lower bound of Omega(m n^{2}) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.

Motivated by map labeling, we study the problem in which we are given a collection of n disks in the plane that grow at possibly different speeds. Whenever two disks meet, the one with the higher index disappears. This problem was introduced by Funke, Krumpe, and Storandt[IWOCA 2016]. We provide the first general subquadratic algorithm for computing the times and the order of disappearance. Our algorithm also works for other shapes (such as rectangles) and in any fixed dimension. Using quadtrees, we provide an alternative algorithm that runs in near linear time, although this second algorithm has a logarithmic dependence on either the ratio of the fastest speed to the slowest speed of disks or the spread of the disk centers (the ratio of the maximum to the minimum distance between them). Our result improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EWCG 2017]. Finally, we give an \Omega(n\log n) lower bound on the problem, showing that our quadtree algorithms are almost tight.

Let C be the unit circle in R^2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k >= 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 <= k <= 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Theta(1/k^(2/3)) for any k.

The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m+n) log^3(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively.

In this paper, we investigate the L_1 geodesic farthest neighbors in a simple polygon P, and address several fundamental problems related to farthest neighbors. Given a subset S subseteq P, an L_1 geodesic farthest neighbor of p in P from S is one that maximizes the length of L_1 shortest path from p in P. Our list of problems include: computing the diameter, radius, center, farthest-neighbor Voronoi diagram, and two-center of S under the L_1 geodesic distance. We show that all these problems can be solved in linear or near-linear time based on our new observations on farthest neighbors and extreme points. Among them, the key observation shows that there are at most four extreme points of any compact subset S subseteq P with respect to the L_1 geodesic distance after removing redundancy.

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L_1 geodesic diameter in O(n^2+h^4) time and the L_1 geodesic center in O((n^4+n^2 h^4)*alpha(n)) time, where alpha(.) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^{7.73}) or O(n^7(h+log(n))) time, and compute the geodesic center in O(n^{12+epsilon}) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L_1 shortest paths in polygonal domains.

The best-case and the worst-case coverage were proposed originally for a single source and destination pair in a sensor network. In this paper, we propose a new coverage measure of the sensor network considering arbitrary paths. Surprisingly, this new measure captures both the best-case and the worst-case coverage of the sensor network simultaneously, enabling us to evaluate the given network in a global viewpoint. Accordingly, we pose the evaluation and the deployment problems; the former is to evaluate the new coverage measure of a given sensor network, and the latter is to find an optimal placement of k additional sensor nodes to improve the coverage for a given positive integer k. We present several algorithms solving the problems that are either centralized or localized with theoretical proofs and simulation results, showing that our algorithms are efficient and easy to implement in practice while the quality of outputs is guaranteed by formal proofs. Our algorithms are based on an interesting relation between our new coverage measure and a certain quantity of a point set, called the bottleneck, which has been relatively well studied in other disciplines. In doing so, we prove that a maximal support path can always be found in the minimum spanning tree; this is another contribution of ours.

We investigate the farthest-site Voronoi diagram of k point sites with respect to the geodesic distance in a polygonal domain of n corners and h (≥ 0) holes. In the case of h=0, Aronov et al. [2] in 1993 proved that there are at most O(k) faces in the diagram and the complexity of the diagram is at most O(n+k). However, any nontrivial upper bound on the geodesic farthest-site Voronoi diagram in a polygonal domain when h > 0 remains unknown afterwards. In this paper, we show that the diagram in a polygonal domain consists of Θ(hk) faces and its total combinatorial complexity is Θ(nk) in the worst case for any h ≥ 1. Interestingly, the worst-case complexity of the diagram is independent from the number h of holes if h ≥ 1 while the maximum possible number of faces is dependent on h rather than on the complexity n of the polygonal domain. Also, we present an O(nk log2(n+k) log k)-time algorithm that constructs the diagram explicitly.

The aperture angle α(x, Q) of a point x∉ Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q ⊂ C is the minimum aperture angle of any x ∈ C ࢨ Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q ⊂ C with aperture angle approximation error (1 - 2/k+1)π. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance σ, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most 1/k+1 sin π/k+1.