World Library  
Flag as Inappropriate
Email this Article

Alpha shape

Article Id: WHEBN0033029175
Reproduction Date:

Title: Alpha shape  
Author: World Heritage Encyclopedia
Language: English
Subject: Computational geometry, Beta skeleton, Convex hull
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Alpha shape

In computational geometry, an alpha shape, or α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points. They were first defined by Edelsbrunner, Kirkpatrick & Seidel (1983). The alpha-shape associated with a set of points is a generalization of the concept of the convex hull, i.e. every convex hull is an alpha-shape but not every alpha shape is a convex hull.

Characterization

For each real number α, define the concept of a generalized disk of radius 1/α as follows:

  • If α = 0, it is a closed half-plane;
  • If α > 0, it is closed disk of radius 1/α;
  • If α < 0, it is the closure of the complement of a disk of radius −1/α.

Then an edge of the alpha-shape is drawn between two members of the finite point set whenever there exists a generalized disk of radius 1/α containing the entire point set and which has the property that the two points lie on its boundary.

If α = 0, then the alpha-shape associated with the finite point set is its ordinary convex hull.

Alpha complex

Alpha shapes are closely related to alpha complexes, subcomplexes of the Delaunay triangulation of the point set.

Each edge or triangle of the Delaunay triangulation may be associated with a characteristic radius, the radius of the smallest empty circle containing the edge or triangle. For each real number α, the α-complex of the given set of points is the simplicial complex formed by the set of edges and triangles whose radii are at most 1/α.

The union of the edges and triangles in the α-complex forms a shape closely resembling the α-shape; however it differs in that it has polygonal edges rather than edges formed from arcs of circles. More specifically, Edelsbrunner (1995) showed that the two shapes are homotopy equivalent. (In this later work, Edelsbrunner used the name "α-shape" to refer to the union of the cells in the α-complex, and instead called the related curvilinear shape an α-body.)

Examples

This technique can be employed to reconstruct a Fermi surface from the electronic Bloch spectral function evaluated at the Fermi level, as obtained from the Green function in a generalised ab-initio study of the problem. The Fermi surface is then defined as the set of reciprocal space points within the first Brillouin zone, where the signal is highest. The definition has the advantage of covering also cases of various forms of disorder.

Fermi surface of bulk Ag: alpha-shape reconstruction from KKR Bloch spectral function reconstruction

See also

References

  • N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, E. P. Mucke, and C. Varela. "Alpha shapes: definition and software". In Proc. Internat. Comput. Geom. Software Workshop 1995, Minneapolis.
  • .
  • .

External links

  • Alpha Shapes in CGAL the Computational Geometry Algorithms Library
  • Description and implementation by Duke University
  • Everything You Always Wanted to Know About Alpha Shapes But Were Afraid to Ask – with illustrations and interactive demonstration
  • Implementation of the 3D alpha-shape for the reconstruction of 3D sets from a point cloud in R
  • Description of the implementation details for alpha shapes - Lecture providing a description of the formal and intuitive aspects of alpha shape implementation
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.