# Alpha shape

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Alpha_shape
> Markdown URL: https://mediated.wiki/source/Alpha_shape.md
> Source: https://en.wikipedia.org/wiki/Alpha_shape
> Source revision: 1311284267
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Approximation to shape of a point cloud}}
{{CS1 config|mode=cs2}}
[[File:ScagnosticsBase.svg|thumb|400px|Convex hull, alpha shape and [minimal spanning tree](/source/minimal_spanning_tree) of a bivariate data set]]
In [computational geometry](/source/computational_geometry), an '''alpha shape''', or '''α-shape''', is a family of piecewise linear simple curves in the [Euclidean plane](/source/Euclidean_plane) associated with the shape of a finite set of points. They were first defined by {{harvtxt|Edelsbrunner|Kirkpatrick|Seidel|1983}}. The alpha-shape associated with a set of points is a generalization of the concept of the [convex hull](/source/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](/source/Closed_set) [half-plane](/source/half-plane);
* If ''α'' > 0, it is a closed disk of radius 1/''α'';
* If ''α''&nbsp;<&nbsp;0, it is the [closure](/source/Closure_(topology)) of the complement of a disk of radius&nbsp;&minus;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&nbsp;1/''α'' that has the two points on its [boundary](/source/Boundary_(topology)) and that contains none of the point set in its [interior](/source/Interior_(topology)).

If ''α''&nbsp;= 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, which are subcomplexes of the [Delaunay triangulation](/source/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](/source/real_number) ''α'', the  ''α''-complex of the given set of points is the [simplicial complex](/source/simplicial_complex) formed by the set of edges and triangles whose radii are at most 1/''α''.

The ''α''-complex is also a subcomplex of the [Čech complex](/source/%C4%8Cech_complex), but computationally more efficient if the [ambient space](/source/ambient_space) has dimension 2 or 3.<ref>{{cite thesis|title=Approximation algorithms for Vietoris-Rips and Čech filtrations|last=Choudhary|first=Aruni|year=2017|publisher=Universität des Saarlandes|doi=10.22028/D291-26959|hdl=20.500.11880/26911}}</ref><ref>{{cite journal|arxiv=2310.00536|title=Computing the alpha complex using dual active set quadratic programming|year=2023|first1=Erik|last1=Carlsson|first2=John|last2=Carlsson|journal=Scientific Reports |volume=14 |issue=1 |page=19824 |doi=10.1038/s41598-024-63971-3 |bibcode=2024NatSR..1419824C }}</ref>

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, {{harvtxt|Edelsbrunner|1995}} showed that the two shapes are [homotopy equivalent](/source/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 ==
[[File:Bulk Ag, Fermi surface.png|thumb|Fermi surface of bulk silver: alpha-shape reconstruction from [KKR](/source/Korringa%E2%80%93Kohn%E2%80%93Rostoker_method) Bloch spectral function reconstruction]]
This technique can be employed to reconstruct a [Fermi surface](/source/Fermi_surface) from the electronic Bloch [spectral function](/source/spectral_function) evaluated at the [Fermi level](/source/Fermi_level), as obtained from the [Green's function](/source/Green's_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](/source/Brillouin_zone), where the signal is highest. 
The definition has the advantage of covering also cases of various forms of disorder.

<!-- Please add the value of alpha used. -->

{{expand section|date=September 2011}}

==See also==
*[Beta skeleton](/source/Beta_skeleton)

== References ==
{{reflist}}
* N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, E. P. Mucke, and C. Varela. "[http://wcl.cs.rpi.edu/papers/b11.pdf Alpha shapes: definition and software]". In ''Proc. Internat. Comput. Geom. Software Workshop 1995'', Minneapolis.
*{{citation
 | last = Edelsbrunner | first = Herbert | author-link = Herbert Edelsbrunner
 | contribution = Smooth surfaces for multi-scale shape representation
 | location = Berlin
 | mr = 1458090
 | pages = 391–412
 | publisher = Springer
 | series = Lecture Notes in Comput. Sci.
 | title = Foundations of software technology and theoretical computer science (Bangalore, 1995)
 | volume = 1026
 | year = 1995}}.
*{{citation
 | last1 = Edelsbrunner | first1 = Herbert | author1-link = Herbert Edelsbrunner
 | last2 = Kirkpatrick | first2 = David G. | author2-link = David G. Kirkpatrick
 | last3 = Seidel | first3 = Raimund | author3-link = Raimund Seidel
 | doi = 10.1109/TIT.1983.1056714
 | issue = 4
 | journal = IEEE Transactions on Information Theory
 | pages = 551–559
 | title = On the shape of a set of points in the plane
 | volume = 29
 | year = 1983}}.

== External links ==
{{commonscat}}
* [http://doc.cgal.org/latest/Alpha_shapes_2/ 2D Alpha Shapes] and [http://doc.cgal.org/latest/Alpha_shapes_3/ 3D Alpha Shapes] in [CGAL](/source/CGAL) the Computational Geometry Algorithms Library
* [http://gudhi.gforge.inria.fr/doc/latest/group__alpha__complex.html Alpha Complex] in the GUDHI library.
* [https://web.archive.org/web/20120402085555/http://biogeometry.duke.edu/software/alphashapes/ Description and implementation by Duke University]
* [http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html Everything You Always Wanted to Know About Alpha Shapes But Were Afraid to Ask] – with illustrations and interactive demonstration
* [https://cran.r-project.org/web/packages/alphashape3d/index.html Implementation of the 3D alpha-shape for the reconstruction of 3D sets from a point cloud in R]
* [https://web.archive.org/web/20110308071257/http://www.mpi-inf.mpg.de/~jgiesen/tch/sem06/Celikik.pdf Description of the implementation details for alpha shapes] – lecture providing a description of the formal and intuitive aspects of alpha shape implementation
* [https://web.archive.org/web/20161011065237/http://research.engineering.wustl.edu/~pless/546/lectures/lecture22.pdf Alpha Hulls, Shapes, and Weighted things] – lecture slides by Robert Pless at the [Washington University in St. Louis](/source/Washington_University_in_St._Louis)

Category:Convex hulls
Category:Computational geometry

---
Adapted from the Wikipedia article [Alpha shape](https://en.wikipedia.org/wiki/Alpha_shape) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Alpha_shape?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.