Khoury, Marc ;
Shewchuk, Jonathan Richard
Fixed Points of the Restricted Delaunay Triangulation Operator
Abstract
The restricted Delaunay triangulation can be conceived as an operator that takes as input a kmanifold (typically smooth) embedded in R^d and a set of points sampled with sufficient density on that manifold, and produces as output a kdimensional 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 2manifold embedded in a highdimensional space R^d, also with modest sampling requirements (especially compared to algorithms that depend on sliver exudation). The latter algorithm builds a nonmanifold 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.
BibTeX  Entry
@InProceedings{khoury_et_al:LIPIcs:2016:5939,
author = {Marc Khoury and Jonathan Richard Shewchuk},
title = {{Fixed Points of the Restricted Delaunay Triangulation Operator}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {47:147:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5939},
URN = {urn:nbn:de:0030drops59396},
doi = {10.4230/LIPIcs.SoCG.2016.47},
annote = {Keywords: restricted Delaunay triangulation, fixed point, manifold reconstruction, surface reconstruction, computational geometry}
}
2016
Keywords: 

restricted Delaunay triangulation, fixed point, manifold reconstruction, surface reconstruction, computational geometry 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 