Convex layers: Difference between revisions

Revision as of 07:40, 23 September 2018

Latest revision as of 23:42, 8 June 2025

(5 intermediate revisions by 3 users not shown)

Line 9:

| 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:

| volume = 5

| year = 2014| arxiv = 1302.5328

| s2cid = 6679520

}}.</ref>

Line 34 ⟶ 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

| 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''', and the convex layers themselves are the depth contours for this notion of data 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 52 ⟶ 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 77 ⟶ 85:

| 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

Line 86 ⟶ 95:

| title = Counting the onion

| volume = 24

| year = 2004}}</ref>| s2cid = 10366666

}}</ref>

==References==