This paper introduces the concept of α-shapes for finite point sets in three-dimensional space. α-shapes are a generalization of the convex hull and are defined using Delaunay triangulations. Each α-shape is a polytope derived from the Delaunay triangulation of the point set, with a parameter α controlling the level of detail. As α decreases, the α-shape shrinks, developing cavities, tunnels, and even holes. The α-shape is defined as the polytope whose boundary consists of triangles, edges, and vertices from the α-exposed simplices of the Delaunay triangulation.
The paper discusses related geometric concepts such as α-hulls, α-diagrams, Delaunay triangulations, and Voronoi diagrams. It also presents an algorithm that constructs the entire family of α-shapes for a given set of points in O(n²) time, where n is the number of points. The algorithm is implemented and discussed in terms of its data structures, robustness, and performance. The paper also explores applications of α-shapes in scientific computing, including the study of molecular structures and the distribution of galaxies. Finally, it considers possible extensions of the α-shape concept to higher dimensions and weighted points.This paper introduces the concept of α-shapes for finite point sets in three-dimensional space. α-shapes are a generalization of the convex hull and are defined using Delaunay triangulations. Each α-shape is a polytope derived from the Delaunay triangulation of the point set, with a parameter α controlling the level of detail. As α decreases, the α-shape shrinks, developing cavities, tunnels, and even holes. The α-shape is defined as the polytope whose boundary consists of triangles, edges, and vertices from the α-exposed simplices of the Delaunay triangulation.
The paper discusses related geometric concepts such as α-hulls, α-diagrams, Delaunay triangulations, and Voronoi diagrams. It also presents an algorithm that constructs the entire family of α-shapes for a given set of points in O(n²) time, where n is the number of points. The algorithm is implemented and discussed in terms of its data structures, robustness, and performance. The paper also explores applications of α-shapes in scientific computing, including the study of molecular structures and the distribution of galaxies. Finally, it considers possible extensions of the α-shape concept to higher dimensions and weighted points.