SpringerLink
Log in

Duality of constrained Voronoi diagrams and Delaunay triangulations

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We introduce theconstrained Voronoi diagram of a planar straight-line graph containingn vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of theconstrained Delaunay triangulation. We briefly discussO(n logn) algorithms for constructing the extended constrained Voronoi diagram.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. A. Bondy and U. S. R. Murty (1976),Graph Theory with Applications, MacMillan, London.

    Google Scholar 

  2. L. P. Chew (1989), Constrained Delaunay triangulations,Algorithmica,4, 97–108.

    Google Scholar 

  3. S. Fortune (1987), A sweepline algorithm for Voronoi diagrams,Algorithmica,2, 153–174.

    Google Scholar 

  4. B. Joe and C. A. Wang (1988), Duality and construction of constrained Voronoi diagrams and Delaunay triangulations, manuscript.

  5. D. G. Kirkpatrick (1979), Efficient computation of continuous skeletons,Proc. 20th Annual Symp. on Foundations of Computer Science, pp. 18–27.

  6. D. T. Lee and R. L. Drysdale (1981), Generalization of Voronoi diagrams in the plane,SIAM J. Comput.,10, 73–87.

    Google Scholar 

  7. D. T. Lee and A. K. Lin (1986), Generalized Delaunay triangulation for planar graphs,Discrete Comput. Geom.,1, 201–217.

    Google Scholar 

  8. F. P. Preparata and M. I. Shamos (1985),Computational Geometry, An Introduction, Springer-Verlag, New York.

    Google Scholar 

  9. R. Seidel (1988), Constrained Delaunay triangulations and Voronoi diagrams with obstacles (extended abstract), Rep. 260, IIG TU, Graz, pp. 178–191.

  10. C. A. Wang and L. K. Schubert (1987), An optimal algorithm for constructing the Delaunay triangulation of a set of line segments,Proc. 3rd ACM Symp. on Computational Geometry, pp. 223–232.

  11. C. K. Yap (1987), AnO(n logn) algorithm for the Voronoi diagram of a set of simple curve segments,Discrete Comput. Geom.,2, 365–393.

    Google Scholar 

Download references

Author information

Author notes

  1. Cao An Wang

    Present address: Department of Computer Science, Memorial University of Newfoundland, A1C 5S7, St. John's, Newfoundland, Canada

Authors and Affiliations

  1. Department of Computing Science, University of Alberta, T6G 2H1, Edmonton, Alberta, Canada

    Barry Joe & Cao An Wang

Authors
  1. Barry Joe
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cao An Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Franco P. Preparata.

This work was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Joe, B., Wang, C.A. Duality of constrained Voronoi diagrams and Delaunay triangulations. Algorithmica 9, 142–155 (1993). https://doi.org/10.1007/BF01188709

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01188709

Key words

Search

Navigation