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.
翻译:我们展示了如何用Delaunay复合体的过滤法来将距离的持久性图接近于以$+$设定的点。 完整的Delaunay复合体可以用来精确地计算这个持久性图, 它的大小可能为$O( ⁇ lcel d/2\ rceil}) 。 相反, 我们的建筑只使用$O( n) implices。 中心思想是将Delaunay复合体连接到逐渐稠密的子取样器上, 将一个递增构造中的翻转体视为以$d+1$为维度。 这个方法可以非常简单和直接地证明几何术语的正确性, 因为最后的过滤是一美元( d+1) 美元- 维维的Voronooi 构造, 类似于标准的Delaunay 过滤复合体。 我们还要展示这个复合体是如何高效地构造的 。