Skip to Main content Skip to Navigation

Equating the witness and restricted Delaunay complexes

Jean-Daniel Boissonnat 1 Ramsay Dyer 1 Arijit Ghosh 1 Steve Oudot 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : It is a well-known fact that the restricted Delaunay and witness complexes may differ when the landmark and witness sets are located on submanifolds of Rd of dimension 3 or more. Currently, the only known way of overcoming this issue consists of building some crude superset of the witness complex, and applying a greedy sliver exudation technique on this superset. Unfortunately, the construction time of the superset depends exponentially on the ambient dimension, which makes the witness complex based approach to manifold reconstruction impractical. This work provides an analysis of the reasons why the restricted Delaunay and witness complexes fail to include each other. From this a new set of conditions naturally arises under which the two complexes are equal.
Document type :
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Marc Glisse Connect in order to contact the contributor
Submitted on : Friday, January 16, 2015 - 6:15:13 PM
Last modification on : Saturday, May 1, 2021 - 3:41:42 AM
Long-term archiving on: : Saturday, September 12, 2015 - 6:30:55 AM


Files produced by the author(s)


  • HAL Id : hal-00772486, version 1



Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, Steve Oudot. Equating the witness and restricted Delaunay complexes. [Research Report] CGL-TR-24, CGL. 2011. ⟨hal-00772486⟩



Record views


Files downloads