This is the authors' abstract. We don't add key points for this paper.
Given a planar straight line graph G with n vertices and a point P₀, locating P₀ means to find the region of the planar subdivision induced by G which contains P₀. 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 log ₂ n comparisons on a data structure which uses O(nlog n) storage, in the worst case. The method rests crucially on a simple partition of each edge of G into O(log n) segments.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Franco P. Preparata (1981) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: