Halfplanar range search in linear space and O(n0.695) query time

H. Edelsbrunner, E. Welzl, Information Processing Letters 23 (1986) 289–293.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Abstract
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
Volume
23
Issue
5
Page
289 - 293
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, 23(5), 289–293. 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 23, no. 5 (1986): 289–93. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar