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 notion of onion decompositions first appears in the computational statistics literature @cite_17 , and several rather brute-force algorithms to compute it have been suggested (see @cite_9 and the references therein). In the computational geometry community, Overmars and van Leeuwen @cite_0 presented the first near-linear time algorithm, requiring @math time. Chazelle @cite_4 improved this to an optimal @math time algorithm. Nielsen @cite_13 gave an output-sensitive algorithm to compute only the outermost @math layers in @math time, where @math is the number of vertices participating on the outermost @math layers. In @math , Chan @cite_16 described an @math expected time algorithm.
@cite_4 @cite_9 @cite_0 @cite_16 @cite_13 @cite_17
2048493433 2234945639 2624483937 2073239623 184591146
Let S be a set of n points in the Euclidean plane. The convex layers of S are the convex polygons obtained by iterating on the following procedure: compute the convex hull of S and remove its vertices from S . This process of peeling a planar point set is central in the study of robust estimators in statistics. It also provides valuable information on the morphology of a set of sites and has proven to be an efficient preconditioning for range search problems. An optimal algorithm is described for computing the convex layers of S. The algorithm runs in 0 (n n) time and requires O(n) space. Also addressed is the problem of determining the depth of a query point within the convex layers of S , i.e., the number of layers that enclose the query point. This is essentially a planar point location problem, for which optimal solutions are therefore known. Taking advantage of structural properties of the problem, however, a much simpler optimal solution is derived. Given a set of n points in the plane, a method is described for constructing a nested sequence of m < n 2 convex polygons based on the points. If the points are a random sample, it is shown that the convex sets share some of the distributional properties of one-dimensional order statistics. An algorithm which requires 0(n3) time and 0(n2) space is described for constructing the sequence of convex sets. We present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of n points in three dimensions, where insertions take O(log3n) expected amortized time, deletions take O(log6n) expected amortized time, and extreme-point queries take O(log2n) worst-case time. This is the first method that guarantees polylogarithmic update and query cost for arbitrary sequences of insertions and deletions, and improves the previous O(ne)-time method by Agarwal and Matousek a decade ago. As a consequence, we obtain similar results for nearest neighbor queries in two dimensions and improved results for numerous fundamental geometric problems (such as levels in three dimensions and dynamic Euclidean minimum spanning trees in the plane). We give an output-sensitive algorithm to compute the first k convex or maximal layers in 0( n log I&) -time where Hk is the number of points participating in the first k layers. Computing only the first k layers is interesting in various problems that arise in computational geometry (k-sets and dually k-levels, k-hulls and dually k-belts), pattern recognition, statistics, operations research, etc.