论文标题
快速近似骨架，并保证欧几里得空间中的任何点云
A fast approximate skeleton with guarantees for any cloud of points in a Euclidean space
论文作者
论文摘要
树重建问题是找到一个嵌入式的直线树，该树近似于$ \ Mathbb {r}^m $中的无组织点云，直到某个错误。解决此问题的实用解决方案将加速具有所需物理特性（例如粘度）的新胶体产品。我们在欧几里得空间中定义了任何有限点云$ c $的近似骨架，并具有理论保证。近似骨架询问$（c）$始终属于$ c $的给定偏移，即$ c $到询问$（c）$的最大距离可能是给定的最大错误。近似骨架中的顶点数接近最佳树中最小数字，按要素2进行。任何无组织的点云$ c $的新近似骨架是在$ c $中的几乎线性时间内计算的。最后，近似骨架的表现优于过去的骨架化算法，该算法的大小和准确性对于大型真实胶束和随机云的重建算法。
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.
