L. J. Guibas, S. Y. Oudot. Reconstruction using Witness Complexes. Proc. 18th ACM-SIAM Sympos. on Discrete Algorithms, pages 1076-1085, 2007. Full version in Discrete and Computational Geometry, 40(3):325-356, 2008 (pdf).

Abstract:

We present a novel reconstruction algorithm that, given an input point set sampled from an object S, builds a one-parameter family of complexes that approximate S at different scales. At a high level, our method is very similar in spirit to Chew's surface meshing algorithm, with one notable difference: the restricted Delaunay triangulation is replaced by the witness complex, which makes our algorithm applicable in any metric space. To prove its correctness on curves and surfaces, we highlight the relationship between the witness complex and the restricted Delaunay triangulation in 2d and in 3d. Specifically, we prove that both complexes are equal in 2d and closely related in 3d, under some mild sampling assumptions.

Bibtex: 

@inproceedings{go-ruwc-07
, author =      {L. J. Guibas and S. Y. Oudot}
, title =       {Reconstruction Using Witness Complexes}
, booktitle =   {Proc. 18th ACM-SIAM Sympos. on Discrete Algorithms}
, pages =	{1076--1085}
, year =        {2007}
}