Prev: P12.7 Next: P12.9

P12.8: Karim, Ramsey
Ramsey L. Karim (University of Maryland, College Park)
Isabelle Joncour (Univ. Grenoble Alps)
Lee Mundy (University of Maryland, College Park)





Theme: Algorithms
Title: Alpha-X: An Alpha Shape-based Hierarchical Clustering Algorithm

This project is an ongoing exploration into the utility of alpha shapes in describing hierarchical clustering. Alpha shapes, a concept introduced by Edelsbrunner and Mucke 1994 that relates to a generalization of convex hulls known as alpha hulls, describe boundaries of regions around point clusters that are associated (point to point) at distances less than some characteristic length scale $\alpha$. Algorithms for finding alpha shapes are based on the Delaunay triangulation of the point set, which leads to the notion of both “positive” space, in the inclusion of these triangles into the shapes, as well as “negative” space, in their exclusion. This well-defined negative space can indicate gaps in point clouds at a given $\alpha$ scale; hence the alpha shape approach can define both over- and under- densities of points. The concept of alpha shapes is a discrete approach and can thus be applied to sets of positions of stars to evaluate stellar clustering and associated voids. One feature we are developing is the representation of point-cloud substructures as $\alpha$ values in tree representations which capture the hierarchical lineage of structure at different values of $\alpha$. With this approach, alpha shapes could be used in an alternate hierarchical cluster detection method that characterizes clusters and their complementary gaps over a range of length scales and naturally yields defined boundaries for these cluster and gap shapes. Similar approaches using this method have been successfully implemented outside of astronomy, in fields such as molecular biology, pattern recognition, and digital shape sampling (Varshney, Brooks, and Wright 1994; Edelsbrunner 2010). Our project will continue to develop and validate this methodology, comparing it to extant methods used within our field to verify that it offers novel and significant analysis products before moving into specific scientific applications.

Link to PDF (may not be available yet): P12-8.pdf