Content deleted Content added
→top: rm para break |
→top: convex hull peeling depth |
||
Line 21:
| volume = 5
| year = 2014}}.</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"/>
Line 39 ⟶ 40:
| publisher = Physica-Verlag
| title = COMPSTAT 1982 5th Symposium held at Toulouse 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
| year = 1982}}</ref>▼
| 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
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
| |||