Shape dimension and approximation from samples

ABSTRACT

There are many scientific and engineering applications where an automatic detection of shape dimension from sample data is necessary. Topological dimensions of shapes constitute an important global feature of them. We present a Voronoi based dimension detection algorithm that assigns a dimension to a sample point which is the topological dimension of the manifold it belongs to. Based on this dimension detection, we also present an algorithm to approximate shapes of arbitrary dimension from their samples. Our empirical results with data sets in three dimensions support our theory.

REFERENCES

• 1: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom.,22, (1999), 481-504.
• 2: Nina Amenta , Marshall Bern , David Eppstein, The crust and the &Bgr;-Skeleton: combinatorial curve reconstruction, Graphical Models and Image Processing, v.60 n.2, p.125-135, March 1, 1998 [doi>10.1006/gmip.1998.0465 ]
• 3: N. Amenta , S. Choi , T. K. Dey , N. Leekha, A simple algorithm for homeomorphic surface reconstruction, Proceedings of the sixteenth annual symposium on Computational geometry, p.213-222, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336207]
• 4: C. L. Bajaj , V. Pascucci , D. R. Schikore, Visualization of scalar topology for structural enhancement, Proceedings of the conference on Visualization '98, p.51-58, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 5: C. Bregler , S. M. Omohundro, Nonlinear manifold learning for visual speech recognition, Proceedings of the Fifth International Conference on Computer Vision, p.494, June 20-23, 1995
• 6: Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336208]
• 7: M. P. Do Carmo. Differential Geometry of Curves and Surfaces, Prentice Hall, 1976.
• 8: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 9: T. K. Dey, S. Funke and E. A. Ramos. Surface reconstruction in almost linear time under locally uniform sampling. European Workshop on Comput. Geom., Berlin, March 2001.
• 10: Tamal K. Dey , Joachim Giesen, Detecting undersampling in surface reconstruction, Proceedings of the seventeenth annual symposium on Computational geometry, p.257-263, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378682]
• 11: Tamal K. Dey , Piyush Kumar, A simple provable algorithm for curve reconstruction, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.893-894, January 17-19, 1999, Baltimore, Maryland, United States
• 12: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 13: Herbert Edelsbrunner , Michael Facello , Jie Liang, On the definition and the construction of pockets in macromolecules, Discrete Applied Mathematics, v.88 n.1-3, p.83-102, Nov. 9, 1998 [doi>10.1016/S0166-218X(98)00067-5 ]
• 14: G. A. Edgar. Measure, Topology and Fractal Geometry, Undergraduate texts in mathematics. Springer-Verlag, New York, 1990.
• 15: Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378636]
• 16: K. J. Falconer, The geometry of fractal sets, Cambridge University Press, New York, NY, 1985
• 17: Joachim Giesen, Curve reconstruction, the traveling salesman problem and Menger's theorem on length, Proceedings of the fifteenth annual symposium on Computational geometry, p.207-216, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304973]
• 18: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 19: B. B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman, New York, 1983.
• 20: Thomas Martinetz , Klaus Schulten, Topology representing networks, Neural Networks, v.7 n.3, p.507-522, 1994 [doi>10.1016/0893-6080(94)90109-0]
• 21: Deborah Silver , Xin Wang, Tracking scalar features in unstructured datasets, Proceedings of the conference on Visualization '98, p.79-86, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 22: Chi-Keung Tang , Gérard Medioni, Extremal feature extraction from 3-D vector and noisy scalar fields, Proceedings of the conference on Visualization '98, p.95-102, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 23: K. M.-K. Yip. KAM : A System for Intelligently Guiding Numerical Experimentation by Computer. The MIT Press, Cambridge, Massachusetts, 1991.
• 24: http://www.cis.ohio-state.edu/~tamaldey/cocone.html.
• 25: http://www.cgal.org.