A fast approximate skeleton with guarantees for any cloud of points in a Euclidean space



Elkin, Yury, Liu, Di and Kurlin, Vitaliy ORCID: 0000-0001-5328-5351
(2020) A fast approximate skeleton with guarantees for any cloud of points in a Euclidean space. In: Topology-based methods in Visualisation 2019.

[img] Text
2007.08900v1.pdf - Author Accepted Manuscript

Download (3MB) | Preview

Abstract

The tree reconstruction problem is to find an embedded straight-line tree that approximates a given cloud of unorganized points in $\mathbb{R}^m$ up to a certain error. A practical solution to this problem will accelerate a discovery of new colloidal products with desired physical properties such as viscosity. We define the Approximate Skeleton of any finite point cloud $C$ in a Euclidean space with theoretical guarantees. The Approximate Skeleton ASk$(C)$ always belongs to a given offset of $C$, i.e. the maximum distance from $C$ to ASk$(C)$ can be a given maximum error. The number of vertices in the Approximate Skeleton is close to the minimum number in an optimal tree by factor 2. The new Approximate Skeleton of any unorganized point cloud $C$ is computed in a near linear time in the number of points in $C$. Finally, the Approximate Skeleton outperforms past skeletonization algorithms on the size and accuracy of reconstruction for a large dataset of real micelles and random clouds.

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: Accepted to topoInvis conference
Uncontrolled Keywords: cs.CG, cs.CG
Depositing User: Symplectic Admin
Date Deposited: 21 Sep 2020 15:50
Last Modified: 18 Jan 2023 23:39
DOI: 10.1007/978-3-030-83500-2_13
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3095224