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

PDF papers
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
pick and add to favorite papersHOMELOGIN (you are user _anon_203939 from group guest) CUMINCAD Papers Powered by SciX Open Publishing Services 1.002