Dominique Attali
ABSTRACT
The main result of this paper is an extension of de Silva's Weak Delaunay Theorem to smoothly embedded curves and surfaces in Euclidean space. Assuming a sufficiently fine sampling, we prove that i + 1 points in the sample span an i-simplex in the restricted Delaunay triangulation iff every subset of the i + 1 points has a weak witness.
- Amenta, N., and Bern, M. 1999. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22, 481--504.Google Scholar
Cross Ref
- Amenta, N., Attali, D., and Devillers, O. 2007. Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. In Proc. 18th Ann. ACM-SIAM Sympos. Discrete Alg. to appear. Google ScholarDigital Library
- Attali, D., Boissonnat, J.-D., and Lieutier, A. 2003. Complexity of the Delaunay triangulation of points on surfaces: the smooth case. In Proc. 19th Ann. Sympos. Comput. Geom., 201--210. Google ScholarDigital Library
- Attali, D., Edelsbrunner, H., Harer, J., and Mileyko, Y. 2007. Alpha-beta witness complexes. Manuscript, Duke Univ., Durham, North Carolina.Google Scholar
- Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., and Taubin, G. 1999. The ball-pivoting algorithm for surface reconstruction. IEEE Trans. Visual. Comput. Graphics 5, 349--359. Google ScholarDigital Library
- Boissonnat, J.-D., Guibas, L. J., and Oudot, S. Y. 2007. Manifold reconstruction in arbitrary dimensions using witness complexes. In Proc. 23rd Ann. Sympos. Comput. Geom. to appear. Google ScholarDigital Library
- Carr, J. C., Beatson, R. K., Cherrie, J. B., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In SIGGRAPH'01 Proceedings, Comput. Graphics, 67--76. Google ScholarDigital Library
- Chazal, F., and Lieutier, A. 2006. Topology guaranteeing manifold reconstruction using distance function to noisy data. In Proc. 22nd Ann. Sympos. Comput. Geom., 112--118. Google ScholarDigital Library
- Chazal, F., Cohen-Steiner, D., and Lieutier, A. 2006. A sampling theory for compact sets in Euclidean space. In Proc. 22nd Ann. Sympos. Comput. Geom., 319--336. Google ScholarDigital Library
- Cheng, S.-W., Dey, T. K., Edelsbrunner, H., Facello, M. A., and Teng, S.-H. 2000. Sliver exudation. J. Assoc. Comput. Mach. 47, 883--904. Google ScholarDigital Library
- Cheng, S.-W., Dey, T. K., and Ramos, E. A. 2005. Manifold reconstruction from point samples. In Proc. 16th Ann. ACM-SIAM Sympos. Discrete Alg., 1018--1027. Google ScholarDigital Library
- De Silva, V., and Carlsson, G. 2004. Topological estimation using witness complexes. In Proc. Sympos. Point-Based Graphics, 157--166. Google ScholarDigital Library
- De Silva, V. 2003. A weak definition of Delaunay triangulation. Manuscript.Google Scholar
- Do Carmo, M. P. 1976. Differential Geometry of Curves and Surfaces. Prentice Hall, Upper Saddle River, New Jersey.Google Scholar
- Edelsbrunner, H., and Shah, N. R. 1997. Triangulating topological spaces. Internat. J. Comput. Geom. Appl. 7, 365--378.Google ScholarCross Ref
- Edelsbrunner, H. 2004. Surface reconstruction by wrapping finite point sets in space. In Discrete and Computational Geometry --- The Goodman-Pollack Festschrift, B. Aronov, S. Basu, J. Pach, and M. Sharir, Eds. Springer-Verlag, Berlin, 379--404.Google Scholar
- Giesen, J., and John, M. 2002. Surface reconstruction based on a dynamical system. Comput. Graphics Forum 21, 363--371.Google ScholarCross Ref
- Guibas, L. J., and Oudot, S. Y. 2007. Reconstruction using witness complexes. In Proc. 18th Ann. ACM-SIAM Sympos. Discrete Alg. to appear. Google ScholarDigital Library
- Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In SIGGRAPH'92 Proceedings, Comput. Graphics, vol. 26, 71--77. Google ScholarDigital Library
- Martinetz, T., and Schulten, K. 1994. Topology representing networks. Neural Networks 7, 507--522. Google ScholarDigital Library
- Milnor, J. 1963. Morse Theory. Princeton Univ. Press, New Jersey.Google Scholar
- Niyogi, P., Smale, S., and Weinberger, S. to appear. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. Google ScholarDigital Library
- Oudot, S. Y. 2007. On the topology of the restricted Delaunay triangulation and witness complexes in higher dimensions. Manuscript, Dept. Comput. Sci., Stanford Univ., California.Google Scholar
- Thibert, B. 2003. Approximation géométrique d'une surface lisse. Applications en géologie structurale. PhD thesis, Université Claude Bernard, Lyon, France.Google Scholar
- Zhao, H., Osher, S., and Fedkiw, R. 2001. Fast surface reconstruction using the level set method. In Proc. 1st IEEE Workshop on Variational and Level Set Methods, 194--202. Google ScholarDigital Library
Index Terms
- Weak witnesses for Delaunay triangulations of submanifolds
Recommendations
Polynomial Surfaces Interpolating Arbitrary Triangulations
Triangular Bézier patches are an important tool for defining smooth surfaces over arbitrary triangular meshes. The previously introduced 4-split method interpolates the vertices of a 2-manifold triangle mesh by a set of tangent plane continuous ...
Conforming weighted delaunay triangulations
Given a set of points together with a set of simplices we show how to compute weights associated with the points such that the weighted Delaunay triangulation of the point set contains the simplices, if possible. For a given triangulated surface, this ...
Flips in Higher Order Delaunay Triangulations
LATIN 2020: Theoretical InformaticsAbstractWe study the flip graph of higher order Delaunay triangulations. A triangulation of a set S of n points in the plane is order-k Delaunay if for every triangle its circumcircle encloses at most k points of S. The flip graph of S has one vertex for ...
Comments