Computing the Voronoi diagram of a subset of sites in linear time from the Voronoi diagram of the full set

The 1989 paper of Aggarwal, Guibas, Saxe, and Shor on linear-time Voronoi diagrams of convex polygons closed with three open problems. Two of them have since been resolved in the literature: constrained Delaunay triangulations of arbitrary simple polygons are now known to be constructible in deterministic $\Theta(n)$ time (Chin and Wang, 1998, after a randomized expected-linear algorithm of Klein and Lingas), and the Delaunay triangulation of $n$ planar points can be computed from their Euclidean minimum spanning tree in $O(n\log^* n)$ expected time (Devillers, 1992) and in deterministic linear time (Chin and Wang, 1998). The surviving open core is the third problem: given the Voronoi diagram of a set $S$ of $n$ planar points and a subset $S_0\subset S$, can the Voronoi diagram of $S_0$ alone be computed in $O(n)$ time? No algorithm beating $\Theta(n\log n)$ is known for arbitrary subsets, and no superlinear lower bound is known; deleting a single site is known to take time linear in the number of its Voronoi neighbors, but that technique does not extend to deleting many sites at once.

Background

The Voronoi diagram of a set $S$ of $n$ point sites in the Euclidean plane partitions the plane into cells, each consisting of the points closer to one site than to all others. Its dual straight-line graph, obtained by connecting every pair of sites with a common boundary edge, is the Delaunay triangulation; equivalently, this is the triangulation of the sites in which the circumcircle of every triangle contains no site in its interior. For arbitrary point sets the diagram costs $\Theta(n\log n)$ time to construct (the sorting-reduction lower bound of Shamos and Hoey), and this bound is tight.

A landmark exception was established by Aggarwal, Guibas, Saxe, and Shor (1989): if the $n$ sites are the vertices of a convex polygon given in cyclic order, the Voronoi diagram can be computed in linear time. Their method computes certain three-dimensional convex hulls in linear time, using the classical lifting map that sends each planar site $(x,y)$ to $(x,y,x^2+y^2)$ on a paraboloid, under which planar Delaunay triangulations correspond to convex hulls. The same techniques yield linear-time algorithms for the furthest-site Voronoi diagram and the medial axis of a convex polygon (the medial axis is the set of points inside a polygon with more than one closest point on the polygon boundary), and for deleting a single site from an arbitrary planar Voronoi diagram in time linear in the number of Voronoi neighbors of the deleted site; this deletion routine already improved Lee's algorithm for higher-order diagrams.

The closing section of that paper posed three open problems, stated for a simple polygon (a closed polygonal chain without self-intersections): two points of such a polygon are visible to each other if the segment joining them lies inside the polygon.

1. The constrained Delaunay triangulation of a simple polygon $P$ is a triangulation of $P$ in which the circumcircle of each triangle contains no vertex of $P$ simultaneously visible from all three vertices of the triangle (the same object has been called a generalized or bounded Delaunay triangulation; the terminology is due to Chew). In 1989 only $O(n\log n)$ algorithms were known (Chew; Lee and Lin; Wang and Schubert), with a linear lower bound, and even the monotone and star-shaped special cases lacked optimal bounds.

2. Given only the Euclidean minimum spanning tree of $n$ points (the spanning tree of minimum total Euclidean edge length, always a subgraph of the Delaunay triangulation), can the Delaunay triangulation be computed faster than $O(n\log n)$? The known gap was between $\Omega(n)$ and $O(n\log n)$.

3. Given the Voronoi diagram of a set $S$ of $n$ points and a subset $S_0\subset S$, can the Voronoi diagram of $S_0$ be computed in $O(n)$ time? No algorithms better than $O(n\log n)$ were known.

Later literature resolved the first two problems. Klein and Lingas (1993/1996) gave a randomized algorithm of linear expected time for the bounded Voronoi diagram of a simple polygon, and Chin and Wang (conference version 1995, journal version 1998) gave a $\Theta(n)$ worst-case deterministic algorithm for the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon, noting that an $O(n)$ deterministic solution had remained open to conjecture; this subsumes the monotone and star-shaped cases. For the second problem, Devillers (1992) showed that the Delaunay triangulation can be computed in $O(n\log^* n)$ expected time given the Euclidean minimum spanning tree, and the deterministic-linear-time version of the same reduction is attributed to Chin and Wang (1998) and is used as a standard tool, for example in the quadtree–Delaunay equivalences of Löffler and Mulzer (2012) and in the 2026 work of Cabello, Chan, and Giannopoulos on Delaunay triangulations with predictions, which generalizes Devillers' technique to arbitrary spanning trees.

For the third problem only the single-site case is settled: besides the original deletion corollary, Junginger and Papadopoulou (2023) solved single-site deletion for abstract Voronoi diagrams (an axiomatic framework of Klein that unifies concrete Voronoi diagrams of points, segments, and other sites) in expected linear time, using intermediate relaxed structures called Voronoi-like diagrams; they also compute, in expected linear time, the order-$(k+1)$ subdivision inside a single region of an order-$k$ Voronoi diagram (the order-$k$ diagram partitions the plane by the set of $k$ nearest sites). None of these results deletes or discards an arbitrary subset of sites at once, and the original paper observed that both this problem and the minimum-spanning-tree problem involve finding constrained Delaunay triangulations of certain simple polygons, a structural hint that has not been carried through for arbitrary subsets.

Problem Statement

Given the Voronoi diagram of a set $S$ of $n$ points in the Euclidean plane, together with the coordinates of the sites, and given a subset $S_0\subset S$ of the sites, determine whether the Voronoi diagram of $S_0$ alone can be computed in $O(n)$ time, that is, in time linear in the size of the input diagram. This is the third open problem stated by Aggarwal, Guibas, Saxe, and Shor (1989): 'Suppose we are given the Voronoi diagram of a set S of n points in the plane and a subset $S_0\subset S$. Can we find the Voronoi diagram of $S_0$ in O(n) time? No known algorithms do better than O(n log n) time.' The subset is arbitrary, so the question covers, for example, deleting a constant fraction of the sites in a single batch rather than one at a time. The standard model is the one in which the Voronoi diagram of $n$ unordered points requires $\Theta(n\log n)$ time. For context, deleting a single site is known to be doable in time linear in the number of Voronoi neighbors of the deleted site, so the open content concerns subsets of unbounded size; the source paper also notes that this problem, like the resolved minimum-spanning-tree variant, involves finding constrained Delaunay triangulations of certain simple polygons.

References

1. Alok Aggarwal, Leonidas J. Guibas, James Saxe, Peter W. Shor, 'A linear-time algorithm for computing the Voronoi diagram of a convex polygon', Discrete & Computational Geometry 4(6):591-604, 1989. DOI: 10.1007/BF02187749, https://doi.org/10.1007/BF02187749
2. L. Paul Chew, 'Constrained Delaunay triangulations', Proceedings of the 3rd Annual ACM Symposium on Computational Geometry (SoCG '87), pp. 215-222, 1987. DOI: 10.1145/41958.41981, https://doi.org/10.1145/41958.41981
3. D. T. Lee, A. K. Lin, 'Generalized Delaunay triangulation for planar graphs', Discrete & Computational Geometry 1(3):201-217, 1986. DOI: 10.1007/BF02187695, https://doi.org/10.1007/BF02187695
4. Rolf Klein, Andrzej Lingas, 'A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon', International Journal of Computational Geometry and Applications 6(3):263-278, 1996. DOI: 10.1142/S0218195996000198, https://doi.org/10.1142/S0218195996000198
5. Cao An Wang, Francis Chin, 'Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time', in Algorithms - ESA '95 (Lecture Notes in Computer Science), pp. 280-294, 1995. DOI: 10.1007/3-540-60313-1_150, https://doi.org/10.1007/3-540-60313-1_150
6. Francis Y. L. Chin, Cao An Wang, 'Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time', SIAM Journal on Computing 28(2):471-486, 1998. DOI: 10.1137/S0097539795285916, https://doi.org/10.1137/S0097539795285916
7. Olivier Devillers, 'Randomization yields simple O(n log* n) algorithms for difficult Omega(n) problems', International Journal of Computational Geometry and Applications 2(1):97-111, 1992. DOI: 10.1142/S021819599200007X, https://doi.org/10.1142/S021819599200007X
8. Maarten Löffler, Wolfgang Mulzer, 'Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent', SIAM Journal on Computing 41(4):941-974, 2012. DOI: 10.1137/110825698, arXiv:1205.4738, https://arxiv.org/abs/1205.4738
9. Kolja Junginger, Evanthia Papadopoulou, 'Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems', Discrete & Computational Geometry 69(4):1040-1078, 2023. DOI: 10.1007/s00454-022-00463-z, https://doi.org/10.1007/s00454-022-00463-z
10. Sergio Cabello, Timothy M. Chan, Panos Giannopoulos, 'Delaunay Triangulations with Predictions', arXiv:2601.08106 (v1, 13 January 2026; accepted at ITCS 2026), 2026. DOI: 10.48550/arXiv.2601.08106, https://arxiv.org/abs/2601.08106
11. Michael Ian Shamos, Dan Hoey, 'Closest-point problems', 16th Annual Symposium on Foundations of Computer Science (FOCS 1975), pp. 151-162, 1975. DOI: 10.1109/sfcs.1975.8, https://doi.org/10.1109/sfcs.1975.8
12. C. Wang, L. Schubert, 'An optimal algorithm for constructing the Delaunay triangulation of a set of line segments', Proceedings of the 3rd Annual ACM Symposium on Computational Geometry (SoCG '87), 1987. DOI: 10.1145/41958.41982, https://doi.org/10.1145/41958.41982