skip to main content
article
Free Access

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

Published:01 April 1985Publication History
Skip Abstract Section

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. 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.Google ScholarGoogle Scholar
  2. 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}).Google ScholarGoogle Scholar
  3. 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.Google ScholarGoogle Scholar
  4. 4 BROWN, K.Q. Voronoi diagrams from convex hulls. Inf. Proc. Lett. 9, 5 (1979), 223-228.Google ScholarGoogle Scholar
  5. 5 DAMPHOUSSE, P. Cartographie topologique--La classification des cartes cellulaires. Unpublished Rep., Univ. of Tours, France.Google ScholarGoogle Scholar
  6. 6 EVEN, S. Algorithmic Combinatorics. Macmillan, N.Y., 1973.Google ScholarGoogle Scholar
  7. 7 GREEN, P. J., AND SIBSON, R. Computing Dirichlet tesselation in the plane. Comput. J. 21, 2 (1977), 168-173.Google ScholarGoogle Scholar
  8. 8 HARARY, F. Graph Theory. Addision-Wesley, Reading, Mass., 1972, p. 105.Google ScholarGoogle Scholar
  9. 9 I~~ANAGA, S., AND KAWADA, Y. Encyclopedic Dictionary of Mathematics, 2nd. ed. MIT Press, Cambridge, Mass., 1968.Google ScholarGoogle Scholar
  10. 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.Google ScholarGoogle Scholar
  11. 11 KIRKPATRICK, D. Optimal search in planar subdivisions. Tech. Rep. 81-13, Dep. of Computer Science, Univ. of British Columbia, 1981. Google ScholarGoogle Scholar
  12. 12 KNUTH, D.E. The Art of Computer Programming, vol. I: Fundamental Algorithms, 2nd. ed. Addision-Wesley, Reading, Mass., 1975. Google ScholarGoogle Scholar
  13. 13 LEE, D.T. Proximity and reachability in the plane. Tech. Rep. R-831, Coordinated Science Lab., Univ. of Illinois, Urbana, I11., 1978.Google ScholarGoogle Scholar
  14. 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.Google ScholarGoogle Scholar
  15. 15 MANTYLA, M. J., AND SULONEN, R. GWB: A solid modeler with Euler operators. IEEE Comput. Graphics Appl. 2, 5 (Sept. 1982), 17-31.Google ScholarGoogle Scholar
  16. 16 MULLER, D. E., AND PREPARATA, F. P. Finding the intersection of two convex polyhedra. Theor. Comput. Sci. 7 (1978), 217-236.Google ScholarGoogle Scholar
  17. 17 PREPARATA, F. P., AND HONG, S.J. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20 (1977), 87-93. Google ScholarGoogle Scholar
  18. 18 SHAMOS, M. I. Computational geometry. Ph.D. Dissertation, Yale University, New Haven, Conn., 1977. Google ScholarGoogle Scholar
  19. 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.Google ScholarGoogle Scholar
  20. 20 WkTSON, D.F. Computing the n-dimensional Delaunay tesselation with application to Voronoi polytopes. Comput ,I. 24, 2 (1981), 167-172.Google ScholarGoogle Scholar

Index Terms

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

            Recommendations

            Comments

            Login options

            Check if you have access through your login credentials or your institution to get full access on this article.

            Sign in

            Full Access

            PDF Format

            View or Download as a PDF file.

            PDF

            eReader

            View online with eReader.

            eReader