Alpha Complex and Union of Growing Disks

​
show disks union
show alpha complex
disk/alpha radius
0.28
show Voronoi tessellation
show full Delaunay complex
​
Generate point cloud
of the type
random
circle
8-shape
with
10
20
40
points.
How might you define a "shape" of a finite set of points? One possibility is to consider the union of disks centered at the points. To study this geometrical object computationally, we can use the alpha complex—a discrete structure that captures, in a way, the same "shape" as the union of the disks (they are homotopy equivalent). In this Demonstration, you can explore the correspondence between those two, as well as the relation to two closely related concepts: Voronoi tessellation and Delaunay triangulation.

Details

The definition of alpha complexes can be found in[1, 2]; alternatively, you can watch a 15-minute tutorial describing these objects on YouTube[3]. In short, the alpha complex of a point cloud
S
of radius
r
is the subcomplex of the Delaunay triangulation consisting of all simplices with radius at most
r
, where the radius of a simplex is the smallest radius of its empty circumcircle. The alpha complex of a point cloud
S
of radius
r
is always homotopy equivalent to the union of circles of radius
r
centered at each point of
S
. In particular, you can notice in this Demonstration that the number of connected components and the number of holes is the same in both of those two objects.
The slider for radius sets both the radius of the disks and the radius of the alpha complex. You can generate point clouds using the "Generate point cloud" button—you can choose the type of the point cloud and the number of points on the setter bars to the right of it. In addition to generating points with the three buttons, all points are Locators, so you can also drag and move them with your cursor and create/delete points.

References

[1] H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, Providence, RI: American Mathematical Society, 2010.
[2] H. Edelsbrunner, A Short Course in Computational Geometry and Topology, Cham: Springer International Publishing, 2014.
[3] O. Draganov. Voronoi Diagram, Delaunay and Alpha Complexes: A Visual Intro[Video]. (Jul 8, 2022) www.youtube.com/watch?v=-XCVn73p3xs.

External Links

Delaunay Triangulation (Wolfram MathWorld)
Voronoi Diagram (Wolfram MathWorld)
Voronoi Diagrams

Permanent Citation

Ondrej Draganov
​
​"Alpha Complex and Union of Growing Disks"​
​http://demonstrations.wolfram.com/AlphaComplexAndUnionOfGrowingDisks/​
​Wolfram Demonstrations Project​
​Published: July 26, 2022