Key points are not available for this paper at this time.
Abstract. 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
David Kirkpatrick (Tue,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: