Herbert Edelsbrunner
Abstract
Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the “shape” of the set. For that purpose, this article introduces the formal notion of the family of α-shapes of a finite point set in R3. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter α ε R controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size n in time 0(n2), worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.
- BOISSONNAT, J. D. 1984. Geometric structures for three-dimensional shape representation. ACM Trans. Graph. 3, 4, 266-286. Google Scholar
- BRISSON, E. 1993. Representing geometric structures in d dimensions: Topology and order. Discr. Comput. Geom. 9, 4, 387-426.Google Scholar
- BRONSTED, A. 1983. An Introduction to Convex Polytopes. Graduate Texts in Mathematics. Springer-Verlag, New York.Google Scholar
- CEN, R. Y., JAMESON, A., LIU, F. AND OSTmKER, J.P. 1990. The universe in a box: Thermal effects in a standard cold dark matter scenario. Astrophys. J. (Letters), L41, 362.Google Scholar
- CORMEN, T. H., LEISERSON, C. E., AND RIVES?, R.L. 1990. Introduction to Algorithms. MIT Press, Cambridge, Mass. Google Scholar
- DELAUNAY, B. 1934. Sur la sphbre vide. lzvestia Akademii Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7 793-800. In French.Google Scholar
- DOBKIN, D. P., AND LASZLO, M.J. 1989. Primitives for the manipulation of three-dimensional subdivisions. Algorithmica 4, 1, 3-32.Google Scholar
- DREBIN, R. A., CARPENTER, L., AND HANRAHAN, P. 1988. Volume rendering. Comput. Graph. 22, 4, 65-74. Google Scholar
- DWYER, R. A. 1991. Higher-dimensional Voronoi diagrams in linear expected time. Discr. Comput. Geom. 6, 4, 343-367. Google Scholar
- DYKSTERHOUSE, M.D. 1992. An alpha-shape view of our universe. Master's thesis, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Urbana, Ill.Google Scholar
- EDELSBRUNNER, H. 1992a. Geometric algorithms. In Handbook of Convex Geometry. North- Holland, Amsterdam, 699 735.Google Scholar
- EDELSBRUNNER, H. 1992b. Weighted alpha shapes. Tech. Rep. UIUCDCS-R-92-1760, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Urbana, Ill. Google Scholar
- EDELSBRUNNER, H. 1987. Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin. Google Scholar
- EDELSBRUNNER, H., KIRKPATRICK, D. G., AND SEIDEL, R. 1983. On the shape of a set of points in the plane. IEEE Trans. Inf. Theor. IT-29, 4, 551-559.Google Scholar
- EDELSBRUNNER, H., AND Mt~CKE, E.P. 1990. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph. 9, 1, 66-104. Google Scholar
- EDELSBRUNNER, H. AND SHAH, N.R. 1992. Incremental topological flipping works for regular triangulations. In Proceedings of the 8th Annual Symposium on Computational Geometry. ACM, New York, 43-52. Google Scholar
- FAIRFIELD, J. 1979. Contoured shape generation: Forms that people see in dot patterns. In Proceedings of the IEEE Conference on Cybernetics and Society, IEEE, New York 60-64.Google Scholar
- FAIRFIELD, J. 1983. Segmenting dot patterns by Voronoi diagram concavity. IEEE Trans. Patt. Anal. Mach. lntell. 5, 1, 104-110.Google Scholar
- GELLER, M. J., AND HUCHRA, J.P. 1989. Mapping the universe. Science 246, 897-903.Google Scholar
- GHELIS, C., AND YON, J. 1982. Protein Folding. Academic Press, New York.Google Scholar
- GIBLIN, P.J. 1981. Graphs, Surfaces, and Homology. 2nd ed. Chapman and Hall, London.Google Scholar
- GUIBAS, L. J., AND STOLrI, J. 1985. Primitives for manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 2, 74-123. Google Scholar
- JARVlS, R.A. 1977. Computing the shape hull of points in the plane. In Proceedings of the IEEE Computing Society Conference on Pattern Recognition and Image Processing. IEEE, New York, 231 241.Google Scholar
- JOE, B. 1991. Construction of three-dimensional Delaunay triangulations using local transformations. Comput. Aided Geom. Des. 8, 2, 123-142. Google Scholar
- JOE, B. 1989. Three-dimensional triangulations from local transformations. SIAM J. Sci. Stat. Comput. 10, 4, 718-741. Google Scholar
- KIRKPATRICK, D. G., AND RADKE, J.D. 1985. A framework for computational morphology. In Computational Geometry. Elsevier North Holland, New York, 234-244.Google Scholar
- LAWSON, C. L. 1977. Software for C1 surface interpolation. In Mathematical Software lI1. Academic Press, New York, 161-194.Google Scholar
- LEE, C. 1991. Regular triangulations of convex polytopes. In Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift. American Mathematical Society, Providence, R.I., 443-456.Google Scholar
- LORENSEN, W. E., AND CLINE, H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. Comput. Graph. 21, 4, 163-169. Google Scholar
- MATOUSEK, J., AND SCHWARZKOPF, O. 1992. Linear optimization queries. In Proceedings of the 8th Annual Symposium on Computational Geometry. ACM, New York, 16-25. Google Scholar
- MATULA, D. W., AND SOKAL, R.R. 1980. Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geograph. Anal. 12, 3, 205-222.Google Scholar
- McMULLEN, P. AND SHErARD, G.C. 1971. Convex Polytopes an the Upper Bound Conjecture. Cambridge University Press, London.Google Scholar
- Moss, W.W. 1967. Some new analytic and graphic approaches to numerical taxonomy, with an example from the Dermanyssidae (Acari). Syst. Zoo. 16, 177-207.Google Scholar
- MOCKE, E.P. 1993. Shapes and implementations in three-dimensional geometry. Ph.D. thesis, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Ubana, Ill. Google Scholar
- PREPARATA, F. P., AND SHAMOS, M. I. 1985. Computational Geometry--An Introduction. Springer-Verlag, New York. Google Scholar
- RICHARDS, F.M. 1991. The protein folding problem. Sci. Am. 264, 1, 54-63.Google Scholar
- SEIDEL, g. 1991. Exact upper bounds for the number of faces in d-dimensional Voronoi diagrams. In Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift. American Mathematical Society, Providence, R.I., 517-530.Google Scholar
- SEIDEL, R. 1986. Constructing higher-dimensional convex hulls in logarithmic cost per face. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing. ACM, New York, 484-507. Google Scholar
- TOUSSAINT, G.T. 1980. The relative neighborhood graph of a finite planar set. Part. Recog. 12, 4, 261-268.Google Scholar
- VELTKAMP, R.C. 1992. Closed object boundaries from scattered points. Ph.D. thesis, Erasmus Univ. Rotterdam.Google Scholar
- VORONOJ, G. 1908. Nouvelles applications de param~tres continus ~ la th~orie des formes quadratiques. Deuxibme M~moire: Recherches sur les parall~llo/~dres primitifs. Journal fur die Reine und Angewandte Mathematik 134, 198-287. In French.Google Scholar
- VORONOI, G. 1907. Nouvelles applications des parambtres continus ~ la th~orie des formes quadratiques. Premier M~moire: Sur quelques propri~t~s de formes quadratiques positives parfaites. Journal fur die Reine und Angewandte Mathematik 133, 97-178. In French.Google Scholar
Recommendations
Screened poisson surface reconstruction
Poisson surface reconstruction creates watertight surfaces from oriented point sets. In this work we extend the technique to explicitly incorporate the points as interpolation constraints. The extension can be interpreted as a generalization of the ...
Marching cubes: A high resolution 3D surface construction algorithm
We present a new algorithm, called marching cubes, that creates triangle models of constant density surfaces from 3D medical data. Using a divide-and-conquer approach to generate inter-slice connectivity, we create a case table that defines triangle ...
Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography
A new paradigm, Random Sample Consensus (RANSAC), for fitting a model to experimental data is introduced. RANSAC is capable of interpreting/smoothing data containing a significant percentage of gross errors, and is thus ideally suited for applications ...
Reviews
Joseph J. O'Rourke
The a -shape S a of a set S of n points in Euclidean 3-space is a polytope whose boundary is a particular collection of triangles, edges, and vertices determined by the points of S . Let T be a subset of S of one, two, or three points. Then the convex hull of T , conv( T ), is part of the boundary 6 S a of the a -shape if and only if the surface of some sphere of radius a includes exactly the points of T while its interior is empty of points of S . Thus a triangle conv( T ) is part of 6 S a if and only if an open a -ball exists that can “erase” all of the triangle but leave its vertices. S a is defined for all 0? a ?? , with S 0 =S and S ? = conv S . Every edge and triangle of S a is present in the Delaunay triangulation D of S , and every edge and triangle in D is present in some S a . If a is varied continuously over its full range starting from ? , the convex hull of S is gradually eaten away by smaller and smaller a -ball erasers, eventually exposing the original set of points. In between, the <__?__Pub Fmt nolinebreak> a -shape<__?__Pub Fmt /nolinebreak> polytope bounds a subcomplex of D that represents a “concrete expression of [the] shape” of S . It has been used for cluster analysis, molecular modeling, and the analysis of medical data, among other applications. This work is one of the few papers coauthored by <__?__Pub Fmt nolinebreak>Edelsbrunner<__?__Pub Fmt /nolinebreak> that proves no theorems. Its aim is to explain the a -shape and related geometric notions for a community of potential users. The mathematical notions are presented with precision and clarity. The paper represents an unusual and welcome balance between theoretical and practical issues. Since all a -shapes are contained in the Delaunay triangulation, D can serve to store all of S a at once. The authors compute D via a simple incremental flipping algorithm. With each edge and triangle of D is associated a single <__?__Pub Fmt nolinebreak> a -interval<__?__Pub Fmt /nolinebreak><__?__Pub Caret1> representing the values of a for which that simplex is present in S a . The elementary but nontrivial geometric computations necessary for implementing the required calculations are explained carefully. They are all expressed in terms of determinant evaluations. Degenerate cases, which often plague geometric algorithms, are handled by the “simulation of simplicity” method pioneered by the authors. This method breaks degeneracies symbolically in a uniform manner, resulting in robust code. The authors have implemented their algorithm, packaged it in an attractive SGI interface, and distributed it freely and widely via ftp. Analyses of runtimes are presented and contrasted with the worst-case O n 2 bound; not surprisingly, most data sets do not exhibit worst-case growth. This superb paper can stand as a model of how to bridge the gap between theory and practice in computational <__?__Pub Fmt nolinebreak>geometry.<__?__Pub Fmt /nolinebreak>
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments