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.
Type de document :
[Research Report] CGL-TR-24, CGL. 2011
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

Contributeur : Marc Glisse <>
Soumis le : vendredi 16 janvier 2015 - 18:15:13
Dernière modification le : samedi 27 janvier 2018 - 01:30:58
Document(s) archivé(s) le : samedi 12 septembre 2015 - 06:30:55


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers