Document Open Access Logo

Restricted Constrained Delaunay Triangulations

Authors Marc Khoury, Jonathan Richard Shewchuk

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.49.pdf
  • Filesize: 1.02 MB
  • 16 pages

Document Identifiers

Author Details

Marc Khoury
  • University of California at Berkeley, CA, USA
Jonathan Richard Shewchuk
  • University of California at Berkeley, CA, USA

Funding

Supported in part by the National Science Foundation under Awards CCF-1423560 and CCF-1909204 and in part by a National Science Foundation Graduate Research Fellowship.

Acknowledgements

This work was initiated at the Workshop on Geometric Algorithms in the Field hosted by the Lorentz Center in Leiden, the Netherlands during June 2014. We thank the organizers - Sándor Fekete, Maarten Löffler, Bettina Speckmann, and Jo Wood - and the Lorentz Center for providing accommodations. We especially thank Bruno Lévy for posing the problem this paper answers, Marc van Kreveld for helpful discussions, and the referees for improving the paper.

Cite AsGet BibTex

Marc Khoury and Jonathan Richard Shewchuk. Restricted Constrained Delaunay Triangulations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.49

Abstract

We introduce the restricted constrained Delaunay triangulation (restricted CDT), a generalization of both the restricted Delaunay triangulation and the constrained Delaunay triangulation. The restricted CDT is a triangulation of a surface whose edges include a set of user-specified constraining segments. We define the restricted CDT to be the dual of a restricted Voronoi diagram defined on a surface that we have extended by topological surgery. We prove several properties of restricted CDTs, including sampling conditions under which the restricted CDT contains every constraining segment and is homeomorphic to the underlying surface.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • restricted Delaunay triangulation
  • constrained Delaunay triangulation
  • surface meshing
  • surface reconstruction
  • topological surgery
  • portals

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nina Amenta and Marshall Bern. Surface Reconstruction by Voronoi Filtering. Discrete & Computational Geometry, 22(4):481-504, June 1999. Google Scholar
  2. Nina Amenta, Marshall W. Bern, and David Eppstein. The Crust and the β-Skeleton: Combinatorial Curve Reconstruction. Graphical Models and Image Processing, 60(2):125-135, March 1998. Google Scholar
  3. Nina Amenta, Sunghee Choi, Tamal K. Dey, and Naveen Leekha. A Simple Algorithm for Homeomorphic Surface Reconstruction. International Journal of Computational Geometry and Applications, 12(1-2):125-141, 2002. Google Scholar
  4. Jean-Daniel Boissonnat, Frédéric Chazal, and Mariette Yvinec. Geometric and Topological Inference, volume 57. Cambridge University Press, September 2018. Google Scholar
  5. Jean-Daniel Boissonnat and Arijit Ghosh. Manifold Reconstruction Using Tangential Delaunay Complexes. Discrete & Computational Geometry, 51(1):221-267, 2014. Google Scholar
  6. Jean-Daniel Boissonnat and Steve Oudot. Provably Good Surface Sampling and Approximation. In Symposium on Geometry Processing, pages 9-18. Eurographics Association, June 2003. Google Scholar
  7. Jean-Daniel Boissonnat and Steve Oudot. Provably Good Sampling and Meshing of Surfaces. Graphical Models, 67(5):405-451, September 2005. Google Scholar
  8. Ho-Lun Cheng, Tamal K. Dey, Herbert Edelsbrunner, and John Sullivan. Dynamic Skin Triangulation. Discrete & Computational Geometry, 25(4):525-568, December 2001. Google Scholar
  9. Siu-Wing Cheng, Tamal K. Dey, and Joshua A. Levine. A Practical Delaunay Meshing Algorithm for a Large Class of Domains. In Proceedings of the 16th International Meshing Roundtable, pages 477-494, Seattle, Washington, October 2007. Google Scholar
  10. Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos. Delaunay Refinement for Piecewise Smooth Complexes. Discrete & Computational Geometry, 43(1):121-166, 2010. Google Scholar
  11. Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Tathagata Ray. Sampling and Meshing a Surface with Guaranteed Topology and Geometry. SIAM Journal on Computing, 37(4):1199-1227, 2007. Google Scholar
  12. Siu-Wing Cheng, Tamal Krishna Dey, and Jonathan Richard Shewchuk. Delaunay Mesh Generation. CRC Press, Boca Raton, Florida, 2012. Google Scholar
  13. L. Paul Chew. Constrained Delaunay Triangulations. Algorithmica, 4(1):97-108, 1989. Google Scholar
  14. Tamal K. Dey. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press, New York, 2007. Google Scholar
  15. Tamal K. Dey and Joshua A. Levine. Delaunay Meshing of Piecewise Smooth Complexes without Expensive Predicates. Algorithms, 2(4):1327-1349, 2009. Google Scholar
  16. Herbert Edelsbrunner and Nimish R. Shah. Triangulating Topological Spaces. International Journal of Computational Geometry and Applications, 7(4):365-378, 1997. Google Scholar
  17. Marc Khoury and Jonathan Richard Shewchuk. Restricted Constrained Delaunay Triangulations. The complete version of this paper, March 2021. URL: https://people.eecs.berkeley.edu/~jrs/papers/rcdt.pdf.
  18. Ron Kimmel and James A. Sethian. Computing Geodesic Paths on Manifolds. Proceedings of the National Academy of Sciences, 95(15):8431-8435, July 1998. Google Scholar
  19. Der-Tsai Lee and Arthur K. Lin. Generalized Delaunay Triangulations for Planar Graphs. Discrete & Computational Geometry, 1:201-217, 1986. Google Scholar
  20. Takashi Maekawa. Computation of Shortest Paths on Free-Form Parametric Surfaces. Journal of Mechanical Design, 118(4):499-508, December 1996. Google Scholar
  21. Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. Variance-Minimizing Transport Plans for Inter-Surface Mapping. ACM Transactions on Graphics, 36(4), 2017. Google Scholar
  22. Steve Oudot, Laurent Rineau, and Mariette Yvinec. Meshing Volumes Bounded by Smooth Surfaces. In Proceedings of the 14th International Meshing Roundtable, pages 203-219, San Diego, California, September 2005. Springer. Google Scholar
  23. Laurent Rineau and Mariette Yvinec. Meshing 3D Domains Bounded by Piecewise Smooth Surfaces. In Proceedings of the 16th International Meshing Roundtable, pages 443-460, Seattle, Washington, 2007. Springer. Google Scholar
  24. Erich Schönhardt. Über die Zerlegung von Dreieckspolyedern in Tetraeder. Mathematische Annalen, 98:309-312, 1928. Google Scholar
  25. Raimund Seidel. Constrained Delaunay Triangulations and Voronoi Diagrams with Obstacles. In H. S. Poingratz and W. Schinnerl, editors, 1978-1988 Ten Years IIG, pages 178-191. Institute for Information Processing, Graz University of Technology, 1988. Google Scholar
  26. Jonathan Richard Shewchuk. Delaunay Refinement Algorithms for Triangular Mesh Generation. Computational Geometry: Theory and Applications, 22(1-3):21-74, 2002. Google Scholar
  27. Jonathan Richard Shewchuk and Brielin C. Brown. Fast Segment Insertion and Incremental Construction of Constrained Delaunay Triangulations. Computational Geometry: Theory and Applications, 48(8):554-574, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact