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 conditions. In this paper, we prove that these results do not extend to higher-dimensional manifolds, even under strong sampling conditions such as uniform point density. On the positive side, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between restricted Delaunay triangulation and witness complex hold on higher-dimensional manifolds as well. We derive from our structural results 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 to be sparse. Its running time is bounded by c(d)n 2, where n is the size of the input point cloud, and c(d) is a constant depending solely (yet exponentially) on the dimension d of the ambient space. Although this running time makes our reconstruction algorithm rather theoretical, recent work has shown that a variant of our approach can be made tractable in arbitrary dimensions, by building upon the results of this paper.
Article PDF
Similar content being viewed by others
References
Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22(4), 481–504 (1999)
Amenta, N., Bern, M., Eppstein, D.: The crust and the β-skeleton: combinatorial curve reconstruction. Graph. Models Image Process. 60, 125–135 (1998)
Amenta, N., Choi, S., Dey, T.K., Leekha, N.: A simple algorithm for homeomorphic surface reconstruction. Int. J. Comput. Geom. Appl. 12, 125–141 (2002)
Attali, D., Edelsbrunner, H., Harer, J., Mileyko, Y.: Alpha–beta witness complexes. In: Proc. 10th Workshop on Algorithms and Data Structures, pp. 386–397 (2007)
Attali, D., Edelsbrunner, H., Mileyko, Y.: Weak witnesses for Delaunay triangulations of submanifolds. In: Proc. ACM Sympos. on Solid and Physical Modeling, pp. 143–150 (2007)
Belkin, M., Niyogi, P.: Semi-supervised learning on Riemannian manifolds. Mach. Learn. 56(1–3), 209–239 (2004)
Boissonnat, J.-D., Oudot, S.: Provably good sampling and meshing of Lipschitz surfaces. In: Proc. 22nd Annu. Sympos. Comput. Geom., pp. 337–346 (2006)
Cazals, F., Giesen, J.: Delaunay triangulation based surface reconstruction. In: Boissonnat, J.D., Teillaud, M. (eds.) Effective Computational Geometry for Curves and Surfaces, pp. 231–273. Springer, Berlin (2006)
Chazal, F., Lieutier, A.: Weak feature size and persistent homology: computing homology of solids in ℝn from noisy data samples. In: Proc. 21st Annual ACM Symposium on Computational Geometry, pp. 255–262 (2005)
Chazal, F., Lieutier, A.: Topology guaranteeing manifold reconstruction using distance function to noisy data. In: Proc. 22nd Annu. Sympos. on Comput. Geom., pp. 112–118 (2006)
Chazal, F., Oudot, S.Y.: Towards persistence-based reconstruction in Euclidean spaces. In: Proc. 24th ACM Sympos. Comput. Geom., pp. 232–241 (2008)
Chazal, F., Cohen-Steiner, D., Lieutier, A.: A sampling theory for compact sets in Euclidean space. In: Proc. 22nd Annu. Sympos. Comput. Geom., pp. 319–326 (2006)
Cheng, S.-W., Dey, T.K., Edelsbrunner, H., Facello, M.A., Teng, S.-H.: Sliver exudation. J. Assoc. Comput. Mach. 47(5), 883–904 (2000)
Cheng, S.-W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. In: Proc. 16th Sympos. Discrete Algorithms, pp. 1018–1027 (2005)
Cheng, S.-W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. Journal version of [14]
Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. In: Proc. 21st ACM Sympos. Comput. Geom., pp. 263–271 (2005)
de Silva, V.: A weak characterisation of the Delaunay triangulation. Geom. Dedic. 135(1), 39–64 (2008)
de Silva, V., Carlsson, G.: Topological estimation using witness complexes. In: Proc. Sympos. Point-Based Graphics, pp. 157–166 (2004)
DeMers, D., Cottrell, G.: Nonlinear dimensionality reduction. Adv. Neural Inf. Process. Syst. 5, 580–587 (1993)
Dey, T.K., Kumar, P.: A simple provable algorithm for curve reconstruction. In: Proc. 10th ACM–SIAM Sympos. Discrete Algorithms, pp. 893–894 (1999)
Dey, T.K., Giesen, J., Goswami, S., Zhao, W.: Shape dimension and approximation from samples. Discrete Comput. Geom. 29, 419–434 (2003)
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer, Berlin (1987)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28, 511–533 (2002)
Federer, H.: Curvature measures. Trans. Am. Math. Soc. 93, 418–491 (1959)
Gao, J., Guibas, L.J., Oudot, S.Y., Wang, Y.: Geodesic Delaunay triangulation and witness complex in the plane. In: Proc. 18th ACM–SIAM Sympos. on Discrete Algorithms, pp. 571–580 (2008)
Giesen, J., Wagner, U.: Shape dimension and intrinsic metric from samples of manifolds with high co-dimension. Discrete Comput. Geom. 32, 245–267 (2004)
Guibas, L.J., Oudot, S.Y.: Reconstruction using witness complexes. Discrete Comput. Geom. 40, 325–356 (2008)
Lee, A.B., Pederson, K.S., Mumford, D.: The nonlinear statistics of high-contrast patches in natural images. Int. J. Comput. Vis. 54(1–3), 83–103 (2003)
Li, X.-Y.: Generating well-shaped d-dimensional Delaunay meshes. Theor. Comput. Sci. 296(1), 145–165 (2003)
Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. 39(1–3), 419–441 (2008)
Roweis, S.T., Saul, L.K.: Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500), 2323–2326 (2000)
Seow, M.-J., Tompkins, R.C., Asari, V.K.: A new nonlinear dimensionality reduction technique for pose and lighting invariant face recognition. In: Proc. IEEE Conf. on Computer Vision and Pattern Recognition—Workshops, p. 160 (2005)
Tenenbaum, J.B., de Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science 290(5500), 2319–2323 (2000)
Vlachos, M., Domeniconi, C., Gunopulos, D., Kollios, G., Koudas, N.: Non-linear dimensionality reduction techniques for classification and visualization. In: Proc. 8th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining, pp. 645–651 (2002)
Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249–274 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was done while S.Y. Oudot was a post-doctoral fellow at Stanford University. His email there is no longer valid.
Rights and permissions
About this article
Cite this article
Boissonnat, JD., Guibas, L.J. & Oudot, S.Y. Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes. Discrete Comput Geom 42, 37–70 (2009). https://doi.org/10.1007/s00454-009-9175-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9175-1