License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.19
URN: urn:nbn:de:0030-drops-72060
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7206/
Go to the corresponding LIPIcs Volume Portal

Boissonnat, Jean-Daniel ; Rouxel-Labbé, Mael ; Wintraecken, Mathijs

Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams

pdf-format:
LIPIcs-SoCG-2017-19.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{boissonnat_et_al:LIPIcs:2017:7206,
  author =	{Jean-Daniel Boissonnat and Mael Rouxel-Labb{\'e} and Mathijs Wintraecken},
  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 =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7206},
  URN =		{urn:nbn:de:0030-drops-72060},
  doi =		{10.4230/LIPIcs.SoCG.2017.19},
  annote =	{Keywords: Riemannian Geometry, Voronoi diagram, Delaunay triangulation}
}

Keywords: Riemannian Geometry, Voronoi diagram, Delaunay triangulation
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI