Alpha shape
{{Short description|Approximation to shape of a point cloud}}
{{CS1 config|mode=cs2}}
File:ScagnosticsBase.svg of a bivariate data set]]
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 {{harvtxt|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 a 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/α that has the two points on its boundary and that contains none of the point set in its interior.
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, which are 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 α-complex is also a subcomplex of the Čech complex, but computationally more efficient if the ambient space has dimension 2 or 3.{{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}}{{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 }}
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. (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 Bloch spectral function reconstruction]]
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'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, where the signal is highest.
The definition has the advantage of covering also cases of various forms of disorder.
{{expand section|date=September 2011}}
See also
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 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