2 Search Results for "Khoury, Marc"

Document
DOI: 10.4230/LIPIcs.SoCG.2021.49
Restricted Constrained Delaunay Triangulations

Authors: Marc Khoury and Jonathan Richard Shewchuk

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.49},
  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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.47
Fixed Points of the Restricted Delaunay Triangulation Operator

Authors: Marc Khoury and Jonathan Richard Shewchuk

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
The restricted Delaunay triangulation can be conceived as an operator that takes as input a k-manifold (typically smooth) embedded in R^d and a set of points sampled with sufficient density on that manifold, and produces as output a k-dimensional triangulation of the manifold, the input points serving as its vertices. What happens if we feed that triangulation back into the operator, replacing the original manifold, while retaining the same set of input points? If k = 2 and the sample points are sufficiently dense, we obtain another triangulation of the manifold. Iterating this process, we soon reach an iteration for which the input and output triangulations are the same. We call this triangulation a fixed point of the restricted Delaunay triangulation operator. With this observation, and a new test for distinguishing "critical points" near the manifold from those near its medial axis, we develop a provably good surface reconstruction algorithm for R^3 with unusually modest sampling requirements. We develop a similar algorithm for constructing a simplicial complex that models a 2-manifold embedded in a high-dimensional space R^d, also with modest sampling requirements (especially compared to algorithms that depend on sliver exudation). The latter algorithm builds a non-manifold representation similar to the flow complex, but made solely of Delaunay simplices. The algorithm avoids the curse of dimensionality: its running time is polynomial, not exponential, in d.
Cite as

Marc Khoury and Jonathan Richard Shewchuk. Fixed Points of the Restricted Delaunay Triangulation Operator. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{khoury_et_al:LIPIcs.SoCG.2016.47,
  author =	{Khoury, Marc and Shewchuk, Jonathan Richard},
  title =	{{Fixed Points of the Restricted Delaunay Triangulation Operator}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.47},
  URN =		{urn:nbn:de:0030-drops-59396},
  doi =		{10.4230/LIPIcs.SoCG.2016.47},
  annote =	{Keywords: restricted Delaunay triangulation, fixed point, manifold reconstruction, surface reconstruction, computational geometry}
}
  • Refine by Author
  • 2 Khoury, Marc
  • 2 Shewchuk, Jonathan Richard

  • Refine by Classification
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 2 restricted Delaunay triangulation
  • 2 surface reconstruction
  • 1 computational geometry
  • 1 constrained Delaunay triangulation
  • 1 fixed point
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2021

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