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. 594606 : 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 pointlocation 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 
Contenttype: text/plain

last changed 
2003/06/02 11:58 
