convex layers

File:Convex layers halfspace.svg

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.{{citation

| last = Chazelle | first = Bernard | authorlink = Bernard Chazelle

| doi = 10.1109/TIT.1985.1057060

| issue = 4

| journal = IEEE Trans. Inf. Theory

| mr = 798557

| pages = 509–517

| title = On the convex layers of a planar set

| volume = 31

| year = 1985| citeseerx = 10.1.1.113.8709 }}

The problem of constructing convex layers has also been called onion peeling or onion decomposition.{{citation

| last1 = Löffler | first1 = Maarten

| last2 = Mulzer | first2 = Wolfgang

| doi = 10.20382/jocg.v5i1a1

| issue = 1

| journal = Journal of Computational Geometry

| mr = 3162956

| pages = 1–13

| title = Unions of onions: preprocessing imprecise points for fast onion decomposition

| volume = 5

| year = 2014| arxiv = 1302.5328

| s2cid = 6679520

}}.

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\backslash log\; n)$.

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.{{citation

| last = Barnett | first = V.

| doi = 10.2307/2344839

| issue = 3

| journal = J. Roy. Statist. Soc. Ser. A

| mr = 0445726

| pages = 318–355

| title = The ordering of multivariate data

| volume = 139

| year = 1976| jstor = 2344839

| s2cid = 117008915

}}{{citation

| last = Eddy

| first = W. F.

| contribution = Convex Hull Peeling

| doi = 10.1007/978-3-642-51461-6_4

| pages = [https://archive.org/details/compstat19825ths0000unse/page/42 42–47]

| publisher = Physica-Verlag

| title = COMPSTAT 1982 5th Symposium held at Toulouse 1982

| year = 1982

| isbn = 978-3-7051-0002-2

| url = https://archive.org/details/compstat19825ths0000unse/page/42

}} 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.{{citation

| last1 = Liu | first1 = Regina Y. | author1-link = Regina Liu

| last2 = Parelius | first2 = Jesse M.

| last3 = Singh | first3 = Kesar

| doi = 10.1214/aos/1018031260

| issue = 3

| journal = Annals of Statistics

| mr = 1724033

| pages = 783–858

| title = Multivariate analysis by data depth: descriptive statistics, graphics and inference

| volume = 27

| year = 1999| doi-access = free

}}

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(\backslash log\; n+k)$ to find $k$ points out of a set of $n$.{{citation

| last1 = Chazelle | first1 = Bernard | author1-link = Bernard Chazelle

| last2 = Guibas | first2 = Leo J. | author2-link = Leonidas J. Guibas

| last3 = Lee | first3 = D. T. | author3-link = Der-Tsai Lee

| doi = 10.1007/BF01934990

| issue = 1

| journal = BIT

| mr = 785806

| pages = 76–90

| title = The power of geometric duality

| volume = 25

| year = 1985}}

The points of an $n\backslash times\; n$ grid have $\backslash Theta(n^\{4/3\})$ convex layers,{{citation

| last1 = Har-Peled | first1 = Sariel | author1-link = Sariel Har-Peled

| last2 = Lidický | first2 = Bernard

| doi = 10.1137/120892660

| issue = 2

| journal = SIAM Journal on Discrete Mathematics

| mr = 3040367

| pages = 650–655

| title = Peeling the grid

| volume = 27

| year = 2013| arxiv = 1302.3200

| s2cid = 15837161 }} as do the same number of uniformly random points within any convex shape.{{citation

| last = Dalal | first = Ketan

| doi = 10.1002/rsa.10114

| issue = 2

| journal = Random Structures & Algorithms

| mr = 2035873

| pages = 155–165

| title = Counting the onion

| volume = 24

| year = 2004| s2cid = 10366666

}}