A One-dimensional Homologically Persistent Skeleton of an Unstructured Point Cloud in any Metric Space

dc.contributor.authorKurlin, Vitaliyen_US
dc.contributor.editorMirela Ben-Chen and Ligang Liuen_US
dc.date.accessioned2015-07-06T05:01:17Z
dc.date.available2015-07-06T05:01:17Z
dc.date.issued2015en_US
dc.description.abstractReal 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).en_US
dc.description.number5en_US
dc.description.sectionheadersCurves and Graphsen_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume34en_US
dc.identifier.doi10.1111/cgf.12713en_US
dc.identifier.pages253-262en_US
dc.identifier.urihttps://doi.org/10.1111/cgf.12713en_US
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.5.1 [Pattern Recognition]en_US
dc.subjectModelsen_US
dc.subjectStructuralen_US
dc.titleA One-dimensional Homologically Persistent Skeleton of an Unstructured Point Cloud in any Metric Spaceen_US
Files