DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2020.75

Generalizing CGAL Periodic Delaunay Triangulations

Authors: Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract

Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity.

Cite as

Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud. Generalizing CGAL Periodic Delaunay Triangulations. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 75:1-75:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{osang_et_al:LIPIcs.ESA.2020.75,
  author =	{Osang, Georg and Rouxel-Labb\'{e}, Mael and Teillaud, Monique},
  title =	{{Generalizing CGAL Periodic Delaunay Triangulations}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{75:1--75:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.75},
  URN =		{urn:nbn:de:0030-drops-129419},
  doi =		{10.4230/LIPIcs.ESA.2020.75},
  annote =	{Keywords: Delaunay triangulation, lattice, algorithm, software, experiments}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2017.19

Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams

Authors: Jean-Daniel Boissonnat, Mael Rouxel-Labbé, and Mathijs Wintraecken

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in R^2 and on surfaces embedded in R^3 as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points P in a domain Omega equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of P to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in Omega under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.

Cite as

Jean-Daniel Boissonnat, Mael Rouxel-Labbé, and Mathijs Wintraecken. Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2017.19,
  author =	{Boissonnat, Jean-Daniel and Rouxel-Labb\'{e}, Mael and Wintraecken, Mathijs},
  title =	{{Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.19},
  URN =		{urn:nbn:de:0030-drops-72060},
  doi =		{10.4230/LIPIcs.SoCG.2017.19},
  annote =	{Keywords: Riemannian Geometry, Voronoi diagram, Delaunay triangulation}
}

Search Results

Documents authored by Rouxel-Labbé, Mael

Generalizing CGAL Periodic Delaunay Triangulations

Abstract

Cite as

Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams

Abstract

Cite as

Thanks for your feedback!

Could not send message