License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.49
URN: urn:nbn:de:0030-drops-138481
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13848/
Go to the corresponding LIPIcs Volume Portal

Khoury, Marc ; Shewchuk, Jonathan Richard

Restricted Constrained Delaunay Triangulations

pdf-format:
LIPIcs-SoCG-2021-49.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{khoury_et_al:LIPIcs.SoCG.2021.49,
  author =	{Khoury, Marc and Shewchuk, Jonathan Richard},
  title =	{{Restricted Constrained Delaunay Triangulations}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13848},
  URN =		{urn:nbn:de:0030-drops-138481},
  doi =		{10.4230/LIPIcs.SoCG.2021.49},
  annote =	{Keywords: restricted Delaunay triangulation, constrained Delaunay triangulation, surface meshing, surface reconstruction, topological surgery, portals}
}

Keywords: restricted Delaunay triangulation, constrained Delaunay triangulation, surface meshing, surface reconstruction, topological surgery, portals
Collection: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue Date: 2021
Date of publication: 02.06.2021

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