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 |
Content-type: text/plain
|
last changed |
2003/06/02 10:24 |
|