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}
}
