Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
Link suggestions feature: 1 link added. |
||
| (One intermediate revision by one other user not shown) | |||
Line 21:
| volume = 5
| year = 2014| arxiv = 1302.5328
| s2cid = 6679520
}}.</ref>
Line 35 ⟶ 36:
| volume = 139
| year = 1976| jstor = 2344839
| s2cid = 117008915
}}</ref><ref>{{citation
| last = Eddy
Line 60 ⟶ 62:
}}</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 84 ⟶ 86:
| 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 93 ⟶ 95:
| title = Counting the onion
| volume = 24
| year = 2004
}}</ref>
==References==
| |||