Halfplanar range search in linear space and O(n0.695) query time
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O (n log 2 (1+√5)−1) time in the worst case, thus improving the best result known before.
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.