Convex layers

Last updated July 25, 2023

In computational geometry, the convex layers of a set of points in the Euclidean plane are a sequence of nested convex polygons having the points as their vertices. The outermost one is the convex hull of the points and the rest are formed in the same way recursively. The innermost layer may be degenerate, consisting only of one or two points.^[1] The problem of constructing convex layers has also been called onion peeling or onion decomposition.^[2]

Although constructing the convex layers by repeatedly finding convex hulls would be slower, it is possible to partition any set of $n$ points into its convex layers in time $O(n\log n)$ .^[1]

An early application of the convex layers was in robust statistics, as a way of identifying outliers and measuring the central tendency of a set of sample points.^[3]^[4] In this context, the number of convex layers surrounding a given point is called its convex hull peeling depth, and the convex layers themselves are the depth contours for this notion of data depth.^[5]

Convex layers may be used as part of an efficient range reporting data structure for listing all of the points in a query half-plane. The points in the half-plane from each successive layer may be found by a binary search to find the most extreme point in the direction of the half-plane, and then searching sequentially from there. Fractional cascading can be used to speed up the binary searches, giving total query time $O(\log n+k)$ to find $k$ points out of a set of $n$ .^[6]

The points of an $n\times n$ grid have $\Theta (n^{4/3})$ convex layers,^[7] as do the same number of uniformly random points within any convex shape.^[8]

Related Research Articles

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD).

A simple polygon that is not convex is called concave, non-convex or reentrant. A concave polygon will always have at least one reflex interior angle—that is, an angle with a measure that is between 180 degrees and 360 degrees exclusive.

<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

In computational geometry, polygon triangulation is the partition of a polygonal area $P$ into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$ .

In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in a given area, the smallest triangle area will be at most inversely proportional to the square of the number of points. His conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown.

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, they are piecewise-linear Jordan curves consisting of finitely many line segments. They include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

<span class="mw-page-title-main">Point-set triangulation</span>

A triangulation of a set of points $in the Euclidean space is a simplicial complex that covers the convex hull of, and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.$

<i>k</i>-d tree Multidimensional search tree for points in k dimensional space

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key and creating point clouds. k-d trees are a special case of binary space partitioning trees.

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes $v$ and $w$ in a tree or directed acyclic graph (DAG) $T$ is the lowest node that has both $v$ and $w$ as descendants, where we define each node to be a descendant of itself.

In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986, combined the idea of cascading, originating in range searching data structures of Lueker (1978) and Willard (1978), with the idea of fractional sampling, which originated in Chazelle (1983). Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events.

<span class="mw-page-title-main">K-set (geometry)</span> Points separated from others by a line

In discrete geometry, a $-set of a finite point set in the Euclidean plane is a subset of elements of that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a -set of a finite point set is a subset of elements that can be separated from the remaining points by a hyperplane. In particular, when, the line or hyperplane that separates a -set from the rest of is a halving line or halving plane .$

<span class="mw-page-title-main">Chan's algorithm</span> Algorithm for finding the convex hull of a set of points in the plane

In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set $of points, in 2- or 3-dimensional space. The algorithm takes time, where is the number of vertices of the output. In the planar case, the algorithm combines an algorithm with Jarvis march, in order to obtain an optimal time. Chan's algorithm is notable because it is much simpler than the Kirkpatrick-Seidel algorithm, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis.$

<span class="mw-page-title-main">Range searching</span>

In computer science, the range searching problem consists of processing a set S of objects, in order to determine which objects from S intersect with a query object, called the range. For example, if S is a set of points corresponding to the coordinates of several cities, find the subset of cities within a given range of latitudes and longitudes.

The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input data elements may be inserted, deleted, or modified. It should be distinguished from the kinetic convex hull, which studies similar problems for continuously moving points. Dynamic convex hull problems may be distinguished by the types of the input data and the allowed types of modification of the input data.

In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of $but worse storage of, where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.$

In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of $line segments with crossings, the Bentley-Ottmann algorithm takes time . In cases where, this is an improvement on a naïve algorithm that tests every pair of segments, which takes .$

Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the Journal of Computational Geometry.

In computational geometry, a CC system or counterclockwise system is a ternary relation $pqr$ introduced by Donald Knuth to model the clockwise ordering of triples of points in general position in the Euclidean plane.

In computational geometry, a point $p$ in a finite set of points $S$ is said to be maximal or non-dominated if there is no other point $q$ in $S$ whose coordinates are all greater than or equal to the corresponding coordinates of $p$ . The maxima of a point set $S$ are all the maximal points of $S$ . The problem of finding all maximal points, sometimes called the problem of the maxima or maxima set problem, has been studied as a variant of the convex hull and orthogonal convex hull problems. It is equivalent to finding the Pareto frontier of a collection of points, and was called the floating-currency problem by Herbert Freeman based on an application involving comparing the relative wealth of individuals with different holdings of multiple currencies.

In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.

References

1 2 Chazelle, Bernard (1985), "On the convex layers of a planar set", IEEE Trans. Inf. Theory, 31 (4): 509–517, CiteSeerX 10.1.1.113.8709 , doi:10.1109/TIT.1985.1057060, MR 0798557
↑ Löffler, Maarten; Mulzer, Wolfgang (2014), "Unions of onions: preprocessing imprecise points for fast onion decomposition", Journal of Computational Geometry, 5 (1): 1–13, arXiv: 1302.5328 , doi:10.20382/jocg.v5i1a1, MR 3162956, S2CID 6679520 .
↑ Barnett, V. (1976), "The ordering of multivariate data", J. Roy. Statist. Soc. Ser. A, 139 (3): 318–355, doi:10.2307/2344839, JSTOR 2344839, MR 0445726, S2CID 117008915
↑ Eddy, W. F. (1982), "Convex Hull Peeling", COMPSTAT 1982 5th Symposium held at Toulouse 1982, Physica-Verlag, pp. 42–47, doi:10.1007/978-3-642-51461-6_4, ISBN 978-3-7051-0002-2
↑ Liu, Regina Y.; Parelius, Jesse M.; Singh, Kesar (1999), "Multivariate analysis by data depth: descriptive statistics, graphics and inference", Annals of Statistics , 27 (3): 783–858, doi: 10.1214/aos/1018031260 , MR 1724033
↑ Chazelle, Bernard; Guibas, Leo J.; Lee, D. T. (1985), "The power of geometric duality", BIT, 25 (1): 76–90, doi:10.1007/BF01934990, MR 0785806
↑ Har-Peled, Sariel; Lidický, Bernard (2013), "Peeling the grid", SIAM Journal on Discrete Mathematics , 27 (2): 650–655, arXiv: 1302.3200 , doi:10.1137/120892660, MR 3040367, S2CID 15837161
↑ Dalal, Ketan (2004), "Counting the onion", Random Structures & Algorithms, 24 (2): 155–165, doi:10.1002/rsa.10114, MR 2035873, S2CID 10366666

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[c85-1] 1 2 Chazelle, Bernard (1985), "On the convex layers of a planar set", IEEE Trans. Inf. Theory, 31 (4): 509–517, CiteSeerX 10.1.1.113.8709 , doi:10.1109/TIT.1985.1057060, MR 0798557

[2] Löffler, Maarten; Mulzer, Wolfgang (2014), "Unions of onions: preprocessing imprecise points for fast onion decomposition", Journal of Computational Geometry, 5 (1): 1–13, arXiv: 1302.5328 , doi:10.20382/jocg.v5i1a1, MR 3162956, S2CID 6679520 .

[3] Barnett, V. (1976), "The ordering of multivariate data", J. Roy. Statist. Soc. Ser. A, 139 (3): 318–355, doi:10.2307/2344839, JSTOR 2344839, MR 0445726, S2CID 117008915

[4] Eddy, W. F. (1982), "Convex Hull Peeling", COMPSTAT 1982 5th Symposium held at Toulouse 1982, Physica-Verlag, pp. 42–47, doi:10.1007/978-3-642-51461-6_4, ISBN 978-3-7051-0002-2

[5] Liu, Regina Y.; Parelius, Jesse M.; Singh, Kesar (1999), "Multivariate analysis by data depth: descriptive statistics, graphics and inference", Annals of Statistics , 27 (3): 783–858, doi: 10.1214/aos/1018031260 , MR 1724033

[6] Chazelle, Bernard; Guibas, Leo J.; Lee, D. T. (1985), "The power of geometric duality", BIT, 25 (1): 76–90, doi:10.1007/BF01934990, MR 0785806

[7] Har-Peled, Sariel; Lidický, Bernard (2013), "Peeling the grid", SIAM Journal on Discrete Mathematics , 27 (2): 650–655, arXiv: 1302.3200 , doi:10.1137/120892660, MR 3040367, S2CID 15837161

[8] Dalal, Ketan (2004), "Counting the onion", Random Structures & Algorithms, 24 (2): 155–165, doi:10.1002/rsa.10114, MR 2035873, S2CID 10366666

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]