Let D be a set of n pairwise disjoint unit disks in the plane. We describe how to build a data structure for D so that for any point set P containing exactly one point from each disk, we can quickly find the onion decomposition (convex layers) of P . Our data structure can be built in O ( n log n ) time and has linear size. Given P , we can find its onion decomposition in O ( n log k ) time, where k is the number of layers. We also provide a matching lower bound. Our solution is based on a recursive space decomposition, combined with a fast algorithm to compute the union of two disjoint onion decompositions.
The framework for preprocessing regions that represent points was first introduced by Held and Mitchell hm-tipps-08 , who show how to store a set of disjoint unit disks in a data structure such that any point set containing one point from each disk can be triangulated in linear time. This result was later extended to arbitrary disjoint regions in the plane by van Kreveld al @cite_3 . L "offler and Snoeyink first showed that the Delaunay triangulation (or its dual, the Voronoi diagram) can also be computed in linear time after preprocessing a set of disjoint unit disks @cite_7 . This result was later extended by Buchin al @cite_8 , and Devillers gives a practical alternative @cite_10 . Ezra and Mulzer @cite_11 show how to preprocess a set of lines in the plane such that the convex hull of a set of points with one point on each line can be computed faster than @math time.
@cite_7 @cite_8 @cite_3 @cite_10 @cite_11
2041094480 1972925770 2102170762 1589450195
An assumption of nearly all algorithms in computational geometry is that the input points are given precisely, so it is interesting to ask what is the value of imprecise information about points. We show how to preprocess a set of n disjoint unit disks in the plane in O(nlogn) time so that if one point per disk is specified with precise coordinates, the Delaunay triangulation can be computed in linear time. From the Delaunay, one can obtain the Gabriel graph and a Euclidean minimum spanning tree; it is interesting to note the roles that these two structures play in our algorithm to quickly compute the Delaunay. Traditional algorithms in computational geometry assume that the input points are given precisely. In practice, data is usually imprecise, but information about the imprecision is often available. In this context, we investigate what the value of this information is. We show here how to preprocess a set of disjoint regions in the plane of total complexity @math in @math time so that if one point per set is specified with precise coordinates, a triangulation of the points can be computed in linear time. In our solution, we solve another problem which we believe to be of independent interest. Given a triangulation with red and blue vertices, we show how to compute a triangulation of only the blue vertices in linear time. We propose a new algorithm that preprocess a set of n disjoint unit disks to be able to compute the Delaunay triangulation in O(n) expected time. Conversely to previous similar results, our algorithm is actually faster than a direct computation in O(n log n) time. Motivated by the desire to cope with data imprecision Loffler (2009) [31], we study methods for taking advantage of preliminary information about point sets in order to speed up the computation of certain structures associated with them. In particular, we study the following problem: given a set L of n lines in the plane, we wish to preprocess L such that later, upon receiving a set P of n points, each of which lies on a distinct line of L, we can construct the convex hull of P efficiently. We show that in quadratic time and space it is possible to construct a data structure on L that enables us to compute the convex hull of any such point set P in O([email protected](n)log^@?n) expected time. If we further assume that the points are ''oblivious'' with respect to the data structure, the running time improves to O([email protected](n)). The same result holds when L is a set of line segments (in general position). We present several extensions, including a trade-off between space and query time and an output-sensitive algorithm. We also study the ''dual problem'' where we show how to efficiently compute the (=