Content deleted Content added
m David Eppstein moved page Convex layer to Convex layers over redirect: The problem is never referred to in the singular. It is like you moved "pants" to "pant". |
Link suggestions feature: 1 link added. |
||
| (15 intermediate revisions by 5 users not shown) | |||
Line 4:
| doi = 10.1109/TIT.1985.1057060
| issue = 4
| journal = IEEE Trans.
| 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 21 ⟶ 20:
| title = Unions of onions: preprocessing imprecise points for fast onion decomposition
| volume = 5
| year = 2014
| 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 [[outlier]]s and measuring the [[central tendency]] of a set of sample points.<ref>{{citation
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 name="c85"/>▼
| 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
}}</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
| isbn = 978-3-7051-0002-2
| url = https://archive.org/details/compstat19825ths0000unse/page/42
}}</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.
| 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
}}</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
| 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}}</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
| 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 }}</ref> as do the same number of uniformly random points within any convex shape.<ref>{{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
}}</ref>
==References==
Line 31 ⟶ 103:
[[Category:Convex hulls]]
[[Category:Computational geometry]]
[[Category:Robust statistics]]
| |||