Three-dimensional alpha shapes

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 &agr;-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 &agr; &egr; 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.

REFERENCES

• 1: Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984 [doi>10.1145/357346.357349]
• 2: BRISSON, E. 1993. Representing geometric structures in d dimensions: Topology and order. Discr. Comput. Geom. 9, 4, 387-426.
• 3: BRONSTED, A. 1983. An Introduction to Convex Polytopes. Graduate Texts in Mathematics. Springer-Verlag, New York.
• 4: 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.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: DELAUNAY, B. 1934. Sur la sphbre vide. lzvestia Akademii Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7 793-800. In French.
• 7: DOBKIN, D. P., AND LASZLO, M.J. 1989. Primitives for the manipulation of three-dimensional subdivisions. Algorithmica 4, 1, 3-32.
• 8: Robert A. Drebin , Loren Carpenter , Pat Hanrahan, Volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.65-74, Aug. 1988
• 9: Rex A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Discrete & Computational Geometry, v.6 n.4, p.343-367, 1991
• 10: 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.
• 11: EDELSBRUNNER, H. 1992a. Geometric algorithms. In Handbook of Convex Geometry. North- Holland, Amsterdam, 699 735.
• 12: Herbert Edelsbrunner, Weighted alpha shapes, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 13: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 14: 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.
• 15: Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
• 16: H. Edelsbrunner , N. R. Shah, Incremental topological flipping works for regular triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.43-52, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142688]
• 17: 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.
• 18: FAIRFIELD, J. 1983. Segmenting dot patterns by Voronoi diagram concavity. IEEE Trans. Patt. Anal. Mach. lntell. 5, 1, 104-110.
• 19: GELLER, M. J., AND HUCHRA, J.P. 1989. Mapping the universe. Science 246, 897-903.
• 20: GHELIS, C., AND YON, J. 1982. Protein Folding. Academic Press, New York.
• 21: GIBLIN, P.J. 1981. Graphs, Surfaces, and Homology. 2nd ed. Chapman and Hall, London.
• 22: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 23: 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.
• 24: Barry Joe, Construction of three-dimensional Delaunay triangulations using local transformations, Computer Aided Geometric Design, v.8 n.2, p.123-142, May 1991 [doi>10.1016/0167-8396(91)90038-D ]
• 25: Barry Joe, Three-dimensional triangulations from local transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.4, p.718-741, July 1989 [doi>10.1137/0910044]
• 26: KIRKPATRICK, D. G., AND RADKE, J.D. 1985. A framework for computational morphology. In Computational Geometry. Elsevier North Holland, New York, 234-244.
• 27: LAWSON, C. L. 1977. Software for C1 surface interpolation. In Mathematical Software lI1. Academic Press, New York, 161-194.
• 28: 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.
• 29: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 30: Jiří Matoušek , Otfried Schwarzkopf, Linear optimization queries, Proceedings of the eighth annual symposium on Computational geometry, p.16-25, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142683]
• 31: 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.
• 32: McMULLEN, P. AND SHErARD, G.C. 1971. Convex Polytopes an the Upper Bound Conjecture. Cambridge University Press, London.
• 33: 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.
• 34: Ernst Peter Mucke, Shapes and implementations in three-dimensional geometry, University of Illinois at Urbana-Champaign, Champaign, IL, 1994
• 35: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 36: RICHARDS, F.M. 1991. The protein folding problem. Sci. Am. 264, 1, 54-63.
• 37: 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.
• 38: R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
• 39: TOUSSAINT, G.T. 1980. The relative neighborhood graph of a finite planar set. Part. Recog. 12, 4, 261-268.
• 40: VELTKAMP, R.C. 1992. Closed object boundaries from scattered points. Ph.D. thesis, Erasmus Univ. Rotterdam.
• 41: 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.
• 42: 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

  J. Computer Applications

General Terms:
Algorithms

Keywords:
Delaunay triangulations, computational graphics, geometric algorithms, point sets, polytopes, robust implementation, scientific computing, scientific visualization, simplicial complexes, simulated perturbation, three-dimensional space