Methods for achieving fast query times in point location data structures
Michael T. Goodrich, Mark Walter Orletsky, Kumar Ramaiyer · 1997
Given a collection S of n line segments in the plane, the planar point location problem is to construct a data structure that can efficiently determine for a given query point p the first segment(s) in S intersected by vertical rays emanating out from p. It is well known that linear-space data structures can be constructed so as to achieve O(log n) query times. But applications, such as those common in geographic information systems, motivate a re-examination of this problem with the goal of improving query times further while also simplifying the methods needed to achieve such query times. In this paper we perform such a re-examination, focusing on the issues that arise in three different classes of point-location query sequences: ffl sequences that are reasonably uniform spatially and temporally (in which case the constant factors in the query times become critical), ffl sequences that are non-uniform spatially or temporally (in which case one desires data structures that adapt to s...