Accession Number : ADA019448

Title :   Location of a Point in a Planar Subdivision and Its Application.

Descriptive Note : Technical rept.,

Corporate Author : ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB

Personal Author(s) : Lee,D. T. ; Preparata,F. P.

Report Date : NOV 1975

Pagination or Media Count : 30

Abstract : Given a subdivision of the plane induced by a planar graph with n vertices, in this paper we consider the problem of identifying which region of the subdivision contains a given test point. We present a search algorithm, called point-location algorithm, which operates on a suitably preprocessed data structure. The search runs in time at most 0(log4sub 25n) sq.), while the preprocessing task runs in time at most 0(n4log sub25n) and requires 0(n) storage. The methods are quite general, since an arbitrary subdivision can be transformed in time at most 0(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. (Author)

Descriptors :   *SEARCH THEORY, *ALGORITHMS, *CONVEX SETS, POINT THEOREM, PREPROCESSING, GEOMETRY, POLYGONS, COMPUTATIONS, TOPOLOGY

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE