Convex layers: Difference between revisions

Revision as of 05:53, 3 August 2017

Latest revision as of 23:42, 8 June 2025

(12 intermediate revisions by 5 users not shown)

Line 4:

| doi = 10.1109/TIT.1985.1057060

| issue = 4

| journal = IEEE Trans. InformInf. 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 }}</ref>

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

| last1 = Löffler | first1 = Maarten

Line 20:

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

| volume = 5

| year = 2014}}| arxiv = 1302.</ref>5328

| s2cid = 6679520

}}.</ref>

Although constructing the convex layers by repeatedly finding convex hulls would be slower, it is possible to partition any set of <math>n</math> points into its convex layers in time <math>O(n\log n)</math>.<ref name="c85"/>

An early application of the convex layers was in [[robust statistics]], as a way of identifying [[outliersoutlier]]s and measuring the [[central tendency]] of a set of sample points.<ref>{{citation

| last = Barnett | first = V.

| doi = 10.2307/2344839

Line 33 ⟶ 35:

| title = The ordering of multivariate data

| volume = 139

| year = 1976}}</ref><ref>{{citation| jstor = 2344839

| s2cid = 117008915

| last = Eddy | first = W. F.

}}</ref><ref>{{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

| year = 1982}}</ref> In this context, the number of convex layers surrounding a given point is called its '''convex hull peeling depth'''.<ref>{{citation

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

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

| year = 1982}}</ref> 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.<ref>{{citation

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

| last2 = Parelius | first2 = Jesse M.

Line 51 ⟶ 59:

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

| volume = 27

| year = 1999}}</ref>| doi-access = free

}}</ref>

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 <math>O(\log n+k)</math> to find <math>k</math> points out of a set of <math>n</math>.<ref>{{citation

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

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

Line 66 ⟶ 75:

| year = 1985}}</ref>

The points of an <math>n\times n</math> grid have <math>\Theta(n^{4/3})</math> convex layers.,<ref>{{citation

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

| last2 = Lidický | first2 = Bernard

| doi = 10.1137/120892660

Line 76 ⟶ 85:

| title = Peeling the grid

| volume = 27

| year = 2013}}</ref>| arxiv = 1302.3200

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

| last = EddyDalal | first = W. F.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

}}</ref>

==References==

Line 83 ⟶ 103:

[[Category:Convex hulls]]

[[Category:Computational geometry]]

[[Category:Robust statistics]]