论文标题
稀疏的Delaunay过滤
A Sparse Delaunay Filtration
论文作者
论文摘要
我们展示了如何使用Delaunay复合物的过滤将距离的持久图近似于$ r^d $中的点。完全可以使用完整的Delaunay复合体来计算此持久图，但它可能具有$ o（n^{\ lceil d/2 \ rceil}）$。相比之下，我们的构造仅使用$ o（n）$简单。核心思想是通过考虑$ d+1 $尺寸中的简单构造中的翻转作为简单，将逐渐密集的子样本上的Delaunay综合体连接起来。这种方法以几何术语提供了非常简单且直接的正确性证明，因为最终过滤是$（d+1）$ - 尺寸的Voronoi结构，类似于标准的Delaunay过滤综合体。我们还展示如何有效地构建这种复合物。
We show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in $R^d$. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size $O(n^{\lceil d/2 \rceil})$. In contrast, our construction uses only $O(n)$ simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in $d+1$ dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a $(d+1)$-dimensional Voronoi construction similar to the standard Delaunay filtration complex. We also, show how this complex can be efficiently constructed.
