On the convex layers of a planar set

Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</tex> be a set of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> points in the Euclidean plane. The convex layers of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</tex> are the convex polygons obtained by iterating on the following procedure: compute the convex hull of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</tex> and remove its vertices from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</tex> . 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0 (n log n)</tex> time and requires <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(n)</tex> space. Also addressed is the problem of determining the depth of a query point within the convex layers of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</tex> , 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.