CoChat
Sign Up
Cited by 2,488Computational Geometry and Mesh GenerationTopological and Geometric Data AnalysisComputer Graphics and Visualization Techniques

Three-dimensional alpha shapes

Open access
Edelsbrunner, Herbert, Mücke, Ernst P.·1994·ACM Transactions on Graphics
DOI 10.1145/174462.156635
Open this paper in CoChat — free accountOpen PDF

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 R 3 . 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(n 2 ) , worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/174462.156635

Cites

38 of 38 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The dimensions of the persistent homology groups that appear in the Homology Inference Theorem are efficiently computable using the persistence algorithm on the filtration of alpha complexes.

    “Indeed, the dimensions of the persistent homology groups that appear in the theorem are efficiently computable using the persistence algorithm on the filtration of alpha complexes [11], [12].”

    From Stability of Persistence Diagrams (2007) · cites this paper as [12]

    Section 3.3, “Alpha Complexes” (page unavailable), defines alpha complexes and states that each is a subcomplex of those at larger alpha values, supporting the filtration part. “Features and Signatures” (page unavailable) describes an efficient way to track connected components, but calls higher-order homology signatures more challenging; it does not describe a persistence algorithm or establish efficient computation of the claimed persistent-homology dimensions. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • The Čech complex and topologically equivalent subcomplexes are delicate to compute because they rely on precise distances between points.

    “However, the Čech complex and various topologically equivalent subcomplexes (e.g., the alpha complex of [13]) are delicate objects to compute, relying on the precise distances between the nodes in E n .”

    From Barcodes: the persistent topology of data (2007) · cites this paper as [13]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 9

  1. [4]4. CEN,R. Y., JAMESON, A., LIU,F. ANDOSTRIKZR, J. P. 1990. The universein a box: Thermal effectsin a standardcold dark matterscenario.Astrophys, J, (Letters), L41, 362.
  2. [5]5. ACMTransactions on Graphics, Vol. 13,No. 1,Jmuary 1994,
  3. [11]11. DYKSTERHO~TSE, M. D. 1992. An alpha-shape view of our universe. Master's thesis, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Urbana, 111.
  4. [18]18. FAIRFIELD,J. 1979. Contoured shape generation: Forms that people see in dot patterns. In Proceedings of the IEEE Conference on Cybernetics and Socidy, IEEE, New York 60-64.
  5. [24]24. S, 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.
  6. [33]33. MCMULLEN, P, AND SHEPARD,G. C, 1971, Convex Polytopes an the Upper Bound Conjecture. Cambridge University Press, London.
  7. [36]36. PREPARATA, F. P., AND SHAMOS, M. L 1985. Computational Geometrj-An lntraduction. Springer-Verlag, New York.
  8. [42]42. VORONOL G. 1908. Nauvelles applications de parametres continus & la th60rie des formes quadratiques. Deuxi&me M6moire: Recherches sur Ies paral16110&dres primitifs. Journal fur die Reine und Angewandte Mathematik 134, 198-287. In French.
  9. [43]43. VORONOI,G. 1907. Nouvelles applications des parami%res continus a la th60rie des formes quadratiques. Premier M6moire: Sur quelques propri6t6s de formes quadratiques positives parfaites, Journal fur die Reine und Angewandte Mathematik 133, 97-178. In French.

Cited by

Sorted by citations

Related

Authors
Edelsbrunner, H., & Mücke, E. P.
Affiliations
University of Illinois Urbana-Champaign (US)
ORCID
Edelsbrunner, Herbert
Venue
ACM Transactions on Graphics
Publisher
Association for Computing Machinery (ACM)
Published
1994-01
Volume
13
Issue
1
Pages
43-72
ISSN
  • 0730-0301 (ISSN-L)
  • 1557-7368
DOI
10.1145/174462.156635
OpenAlex
W2078290150
Cited by
2,488
References
38
Citations by year
2026: 119 · 2025: 152 · 2024: 126 · 2023: 105 · 2022: 98 · 2021: 124 · 2020: 100 · 2019: 94 · 2018: 93 · 2017: 88 · 2016: 95 · 2015: 84 · 2014: 94 · 2013: 93 · 2012: 80
FWCI
33.11
Type
journal article
Language
en
Open access
Licence
Locations
ACM Transactions on Graphics (publishedVersion, public-domain)
Funders
  • National Science Foundation (9118874, 8921421)
  • National Centre for Supercomputing Applications
  • University of Illinois at Urbana-Champaign
Topics
  • Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computational Geometry and Mesh Generation
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Topological and Geometric Data Analysis
  • Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
Keywords
alpha shapes, finite point sets, Delaunay triangulation, polytopes, shape recovery, level of detail, computational geometry

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review