Location of a point in a planar subdivision and its applications

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((log n)2), while the preprocessing task runs in time at most 0(n log n) 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.

REFERENCES

• 1: N. Ketelsen, Triangular tile identification, CS 389 course project, Department of Computer Science, University of Illinois, Urbana, Illinois, Dec. 1973.
• 2: H. J. Shamos, "Problems in Computational Geometry," Department of Computer Science, Yale University, New Haven, Connecticut, May 1975.
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: D. T. Lee and F. P. Preparata, "Location of a point on a planar subdivision and its applications," Coordinated Science Laboratory Report R-699, University of Illinois, Urbana, Illinois, Nov. 1975.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Theory

Keywords:
Analysis of algorithms, Computational complexity, Computational geometry, Inclusion in polygon, Planar region identification, Point location, Spatial convex inclusion