Skeletonisation Algorithms for Unorganised Point Clouds with Theoretical Guarantees
share
Real datasets often come in the form of an unorganised cloud of points. An overall shape of such data is hard to visualise when data points are given by coordinates in a high-dimensional Euclidean space. More general data can be represented by an abstract graph with weights or distances on links between data points. The skeletonisation problem for a point cloud is to find a graph or a skeleton that correctly represents the shape of a cloud. This paper compares three algorithms that solve the data skeletonisation problem for a general cloud with topological and geometric guarantees. First, the Mapper algorithm outputs a network of interlinked clusters. Second, the α-Reeb algorithm discretises the classical Reeb graph and can be applied to discrete clouds at different scales α. The third algorithm HoPeS produces a Homologically Persistent Skeleton without any extra parameters. HoPeS represents the 1-dimensional shape of a cloud at any scale by the Optimality Theorem. The Reconstruction Theorem gives conditions on a noisy sample of a graph when HoPeS provides a reconstructed graph with a correct homotopy type and within a small offset of the sample. The experiments on synthetic and real data show that HoPeS outperforms the other algorithms on several topological and geometric measures.
READ FULL TEXT