Answers are grounded in this paper and cite their sources.
A planar subdivision is any partition of the plane into (possibly unbounded) polygonal regions. The subdivision search problem is the following: given a subdivision S with n line segments and a query point P, determine which region of S contains P. We present a practical algorithm for subdivision search that achieves the same (optimal) worst case complexity bounds as the significantly more complex algorithm of Lipton and Tarjan, namely O (log n) search time with O (n) storage. Our subdivision search structure can be constructed in linear time from the subdivision representation used in many applications. Key words, computational geometry, analysis of algorithms, point location, planar graphs, hierarchical search
No takes yet. Share an insight, caveat, or question.
David Kirkpatrick (1983) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: