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

ABSTRACT

The following problem is discussed: 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 griven sites and then locating the query point inone of its regions. Two algorithms are given, one that constructs the Voronoi diagram in O(n log n) time, and another that inserts a new sit on O(n) time. Both are based on the use of the Voronoi dual, or 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 sufficients for building and modifying arbitrary diagrams.

REFERENCES

• 1: BAUMGART, B.G. A polyhedron representation for computer vision. In 1975 National Computer Conference. AFIPS Conference Proceedings, vol. 44. AFIPS Press, Arlington, Va., 1975, pp. 589- 596.
• 2: BOOTS, B.N. Delaunay triangles: An alternative approach to point pattern analysis. In Proc. Assoc. Am. Geogr. 6 (1974), 26-29 (as cited by {20}).
• 3: BRMD, I. C., HILLYARD, R. C., AND STROUD, I. A. Stepwise construction of polyhedra in geometric modeling. In Mathematical Methods in Computer Graphics and Design, K. W. Brodlie, Ed. Academic Press, London, 1980, pp. 123-141.
• 4: BROWN, K.Q. Voronoi diagrams from convex hulls. Inf. Proc. Lett. 9, 5 (1979), 223-228.
• 5: DAMPHOUSSE, P. Cartographie topologique--La classification des cartes cellulaires. Unpublished Rep., Univ. of Tours, France.
• 6: EVEN, S. Algorithmic Combinatorics. Macmillan, N.Y., 1973.
• 7: GREEN, P. J., AND SIBSON, R. Computing Dirichlet tesselation in the plane. Comput. J. 21, 2 (1977), 168-173.
• 8: HARARY, F. Graph Theory. Addision-Wesley, Reading, Mass., 1972, p. 105.
• 9: I~~ANAGA, S., AND KAWADA, Y. Encyclopedic Dictionary of Mathematics, 2nd. ed. MIT Press, Cambridge, Mass., 1968.
• 10: KIRKPATRICK, D. Efficient computation of continuous skeletons. In Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science (San Juan, Puerto Rico, Oct. 1979), IEEE, New York, pp. 18-27.
• 11: David G. Kirkpatrick, Optimal Search in Planar Subdivisions, University of British Columbia, Vancouver, BC, Canada, 1981
• 12: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 13: LEE, D.T. Proximity and reachability in the plane. Tech. Rep. R-831, Coordinated Science Lab., Univ. of Illinois, Urbana, I11., 1978.
• 14: LEE, D. W., AND SCHACHTER, B.J. Two algorithms for constructing the Delaunay triangulation. Int. J. Comput. Inf. Sci. 9, 3 (1980), 219-242.
• 15: MANTYLA, M. J., AND SULONEN, R. GWB: A solid modeler with Euler operators. IEEE Comput. Graphics Appl. 2, 5 (Sept. 1982), 17-31.
• 16: MULLER, D. E., AND PREPARATA, F. P. Finding the intersection of two convex polyhedra. Theor. Comput. Sci. 7 (1978), 217-236.
• 17: 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]
• 18: Michael Ian Shamos, Computational geometry., 1978
• 19: SHAMOS, M. I., AND HOEV, D. Closest-point problems. In Proceedings o{ the 16th Annual IEEE Symposium on Foundations of Computer Science (Berkeley, CaliL, Oct. 1975), IEEE, New York, pp. 151-162.
• 20: WkTSON, D.F. Computing the n-dimensional Delaunay tesselation with application to Voronoi polytopes. Comput ,I. 24, 2 (1981), 167-172.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory

Keywords:
Euler operators, Voronoi and Delaunay diagrams, closest point, computational topology, convex hull, geometric primitives, nearest neighbours, planar graphs, point location, representation of polynedra, trianglations