CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

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 08:24
HOMELOGIN (you are user _anon_481605 from group guest) Works Powered by SciX Open Publishing Services 1.002