authors 
Preparata, Franco P. 
year 
1979 
title 
A New Approach to Planar Point Location 
source 
August, 1979. 21 [3] p. : ill. includes bibliography 
summary 
Given a planar straight line graph G with n vertices and a point PO, locating PO means to find the region of the planar subdivision induced by G which contains PO. 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 O(log 2n) 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 
keywords 
algorithms, data structures, point inclusion, computational geometry, graphs 
series 
CADline 
references 
Contenttype: text/plain

last changed 
2003/06/02 08:24 
