Skip to main content

Research Repository

Advanced Search

A one-dimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space

Kurlin, Vitaliy

A one-dimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space Thumbnail


Authors

Vitaliy Kurlin



Abstract

Real data are often given as a noisy unstructured point cloud, which is hard to visualize. The important problem is to represent topological structures hidden in a cloud by using skeletons with cycles. All past skeletonization methods require extra parameters such as a scale or a noise bound. We define a homologically persistent skeleton, which depends only on a cloud of points and contains optimal subgraphs representing 1-dimensional cycles in the cloud across all scales. The full skeleton is a universal structure encoding topological persistence of cycles directly on the cloud. Hence a 1-dimensional shape of a cloud can be now easily predicted by visualizing our skeleton instead of guessing a scale for the original unstructured cloud. We derive more subgraphs to reconstruct provably close approximations to an unknown graph given only by a noisy sample in any metric space. For a cloud of n points in the plane, the full skeleton and all its important subgraphs can be computed in time O(n log n).

Citation

Kurlin, V. (2015). A one-dimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space. Computer Graphics Forum, 34(5), 253-262. https://doi.org/10.1111/cgf.12713

Journal Article Type Article
Publication Date Aug 10, 2015
Deposit Date Sep 18, 2015
Publicly Available Date Mar 29, 2024
Journal Computer Graphics Forum
Print ISSN 0167-7055
Electronic ISSN 1467-8659
Publisher Wiley
Peer Reviewed Peer Reviewed
Volume 34
Issue 5
Pages 253-262
DOI https://doi.org/10.1111/cgf.12713
Keywords Categories and Subject Descriptors (according to ACM CCS), I.5.1 [Pattern Recognition]: Models—Structural.

Files

Accepted Journal Article (3.6 Mb)
PDF

Copyright Statement
This is the accepted version of the following article: Kurlin, V. (2015), A one-dimensional homologically persistent skeleton of an unstructured point cloud in any metric space. Computer Graphics Forum, 34(5): 253-262, which has been published in final form at http://dx.doi.org/10.1111/cgf.12713. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.





You might also like



Downloadable Citations