TY - GEN
T1 - Reconstruction using witness complexes
AU - Guibas, Leonidas J.
AU - Oudot, Steve Y.
N1 - Publisher Copyright:
Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.
PY - 2007/1/1
Y1 - 2007/1/1
N2 - We present a novel reconstruction algorithm that, given an input point set sampled from an object S, builds a oneparameter 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.
AB - We present a novel reconstruction algorithm that, given an input point set sampled from an object S, builds a oneparameter 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.
UR - https://www.scopus.com/pages/publications/84969132729
M3 - Conference contribution
AN - SCOPUS:84969132729
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1076
EP - 1085
BT - Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PB - Association for Computing Machinery
T2 - 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Y2 - 7 January 2007 through 9 January 2007
ER -