Content deleted Content added
Citation bot (talk | contribs) Add: s2cid. | Use this bot. Report bugs. | #UCB_CommandLine 77/8263 |
Link suggestions feature: 1 link added. |
||
Line 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
| |||