|
J.-D. Boissonnat, L. J. Guibas, and S. Y. Oudot. Manifold Reconstruction in Arbitrary Dimensions using Witness
Complexes. Proc. 23rd ACM Sympos. on Comput. Geom., pages 194-203, 2007.
Full version in Discrete and Computational Geometry, 42(1):37-70, 2009
(pdf).
Abstract:
It is a well-established fact that the witness complex is closely
related to the restricted Delaunay triangulation in low
dimensions. Specifically, it has been proved that the witness complex
coincides with the restricted Delaunay triangulation on curves, and is
still a subset of it on surfaces, under mild sampling
assumptions. Unfortunately, these results do not extend to
higher-dimensional manifolds, even under stronger sampling
conditions. In this paper, we show how the sets of witnesses and
landmarks can be enriched, so that the nice relations that exist
between both complexes still hold on higher-dimensional manifolds. We
also use our structural results to devise an algorithm that
reconstructs manifolds of any arbitrary dimension or co-dimension at
different scales. The algorithm combines a farthest-point refinement
scheme with a vertex pumping strategy. It is very simple conceptually,
and it does not require the input point sample $W$ to be sparse. Its
time complexity is bounded by $c(d) |W|^2$, where $c(d)$ is a constant
depending solely on the dimension $d$ of the ambient space.
Bibtex:
@inproceedings{bgo-mraduwc-07
, author = {J.-D. Boissonnat and L. J. Guibas and S. Y. Oudot}
, title = {Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes}
, booktitle = {Proc. 23rd ACM Sympos. on Comput. Geom.}
, year = {2007}
}
|
 |