Equating the witness and restricted Delaunay complexes

Jean-Daniel Boissonnat (1) , Ramsay Dyer (1) , Arijit Ghosh (1) , Steve Oudot (1)

1 GEOMETRICA - Geometric computing

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.

Domaines: Géométrie algorithmique [cs.CG]

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⟩