Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams

ABSTRACT

We discuss the following problem: given n points in the plane (the “sites”), and an arbitrary query point q, find the site that is closest to q. This problem can be solved by constructing the Voronoi diagram of the given sites, and then locating the query point in one of its regions. We give two algorithms, one that constructs the Voronoi diagram in O(n lg n) time, and another that inserts a new site in O(n) time. Both are based on the use of the Voronoi dual, the Delaunay triangulation, and are simple enough to be of practical value. The simplicity of both algorithms can be attributed to the separation of the geometrical and topological aspects of the problem, and to the use of two simple but powerful primitives, a geometric predicate and an operator for manipulating the topology of the diagram. The topology is represented by a new data structure for generalized diagrams, that is embeddings of graphs in two-dimensional manifolds. This structure represents simultaneously an embedding, its dual, and its mirror-image. Furthermore, just two operators are sufficient for building and modifying arbitrary diagrams.

REFERENCES

• 1: Baumgart, B. G. A Polyhedron Representation for Computer Vision. AFIPS Conference Proceedings, Vol. 44, 1975 National Computer Conference, pp. 589-596..
• 2: Braid, I. C., Hillyard, R. C., and Stroud, I. A. Stepwise construction of Polyhedra in Geometric Modeling; in Brodlie, K. W. (ed.), Mathematical Methods in Computer Graphics and Design. Academic Press, London, 1980, pp. 123-141..
• 3: Even, S. Algorithmic Combinatorics. Macmillan, N. Y., 1973..
• 4: Green, P. J., and Sibson, R. Computing Dirichlet Tesselation in the Plane. Computer Journal, Vol. 21, no. 2, 1977, pp. 168-173..
• 5: Harary, F. Graph Theory. Addison-Wesley, 1972, p. 105..
• 6: Iyanaga, S., and Kawada, Y. Encyclopedic Dictionary of Mathematics (2nd. ed.). MIT Press, Cambridge, Mass., 1968..
• 7: David G. Kirkpatrick, Optimal Search in Planar Subdivisions, University of British Columbia, Vancouver, BC, Canada, 1981
• 8: Kirkpatrick, D. Efficient Computaion of Continuous Skeletons. Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979, pp. 18-27..
• 9: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 10: Lee, D. T. Proximity and Reachability in the Plane. Report R-831, Coordinated Science Laboratory, University of Illinois, Urbana, 1978..
• 11: Mantyla, M. J., and Sulonen, R. GWB: a Solid Modeler with Euler Operators. IEEE Computer Graphics and Applications, Vol. 2 N. 5 (September 1982) pp. 17-31..
• 12: Muller, D. E., and Preparata, F. P. Finding the Intersection of Two Convex Polyhedra. Theoretical Computer Science Vol. 7, 1978, pp. 217-236..
• 13: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 14: Michael Ian Shamos, Computational geometry., 1978
• 15: Shamos, M. I., and and Hoey, D. Closest-Point Problems. 16th Annual Symposium on Foundations of Computer Science, 1975, pp. 151-162..

INDEX TERMS

Primary 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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Theory