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 Lee, D. T. and Preparata, Franco P.
year 1977
title Location of a Point in a Planar Subdivision and its Applications
source SIAM Journal of Computing. September, 1977. vol. 6: pp. 594-606 : ill. includes bibliography
summary Given a subdivision of the plane induced by a planar graph with n vertices, in this paper the problem of identifying which region of the subdivision contains a given test points is considered. A search algorithm, called point-location algorithm, which operates on a suitably preprocessed data structure is presented. The search runs in time at most O((log n)2), while the preprocessing task runs in time at most O(n log n) and requires O(n) storage. The methods are quite general, since an arbitrary subdivision can be transformed in time at most O(n log n) into one to which the preprocessing procedure is applicable. This solution of the point location problem yields interesting and efficient solutions of other geometric problems, such as spatial convex inclusion and inclusion in an arbitrary polygon
keywords computational geometry, algorithms, analysis, graphs, point inclusion
series CADline
references Content-type: text/plain
last changed 2003/06/02 11:58
HOMELOGIN (you are user _anon_429127 from group guest) Works Powered by SciX Open Publishing Services 1.002