A New Approach to Planar Point Location

Given a planar straight line graph G with n vertices and a point $P_0 $, locating $P_0 $ means to find the region of the planar subdivision induced by G which contains $P_0 $. Recently, Lipton and Tarjan presented a brilliant but extremely complex point location algorithm which runs in time $O(\log n)$ on a data structure using $O(n)$ storage. This paper presents a practical algorithm which runs in less than $6\lceil {\log _2 n} \rceil $ comparisons on a data structure which uses $O(n\log n)$ storage, in the worst case. The method rests crucially on a simple partition of each edge of G into $O(\log n)$ segments.