Halfplanar range search in linear space and O(n0.695) query time
Edelsbrunner H, Welzl E. 1986. Halfplanar range search in linear space and O(n0.695) query time. Information Processing Letters. 23(5), 289–293.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Author
Edelsbrunner, HerbertISTA 
;
Welzl, Emo
;
Welzl, EmoAbstract
Let S denote a set of n points in the Euclidean plane. A halfplanar range query specifies a halfplane h and requires the determination of the number of points in S which are contained in h. A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O(nlog2(1+√5)−1) time in the worst case, thus improving the best result known before. The structure can be built in O(n log n) time.
Publishing Year
Date Published
1986-11-24
Journal Title
Information Processing Letters
Publisher
Elsevier
Acknowledgement
We thank W. Bucher for help in the analysis of the time complexity of the query algorithm.
Volume
23
Issue
5
Page
289 - 293
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Welzl E. Halfplanar range search in linear space and O(n0.695) query time. Information Processing Letters. 1986;23(5):289-293. doi:10.1016/0020-0190(86)90088-8
Edelsbrunner, H., & Welzl, E. (1986). Halfplanar range search in linear space and O(n0.695) query time. Information Processing Letters. Elsevier. https://doi.org/10.1016/0020-0190(86)90088-8
Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear Space and O(N0.695) Query Time.” Information Processing Letters. Elsevier, 1986. https://doi.org/10.1016/0020-0190(86)90088-8.
H. Edelsbrunner and E. Welzl, “Halfplanar range search in linear space and O(n0.695) query time,” Information Processing Letters, vol. 23, no. 5. Elsevier, pp. 289–293, 1986.
Edelsbrunner H, Welzl E. 1986. Halfplanar range search in linear space and O(n0.695) query time. Information Processing Letters. 23(5), 289–293.
Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear Space and O(N0.695) Query Time.” Information Processing Letters, vol. 23, no. 5, Elsevier, 1986, pp. 289–93, doi:10.1016/0020-0190(86)90088-8.
Google Scholar