The alpha complex is a subset of the Delaunay triangulation and is often used in computational geometry and topology. One of the main drawbacks of using the alpha complex is that it is non-monotone, in the sense that if ${\cal X}\subset{\cal X}'$ it is not necessarily (and generically not) the case that the corresponding alpha complexes satisfy ${\cal A}_r({\cal X})\subset{\cal A}_r({\cal X}')$. The lack of monotonicity may introduce significant computational costs when using the alpha complex, and in some cases even render it unusable. In this work we present a new construction based on the alpha complex, that is homotopy equivalent to the alpha complex while maintaining monotonicity. We provide the formal definitions and algorithms required to construct this complex, and to compute its homology. In addition, we analyze the size of this complex in order to argue that it is not significantly more costly to use than the standard alpha complex.
翻译：阿尔法综合体是Delaunay三角图的子集,常常用于计算几何和地形。使用阿尔法综合体的主要缺点之一是它是非单色的,也就是说,如果美元为$$$cal X ⁇ ⁇ subset_calX}$,那么相应的阿尔法综合体不一定(而且一般而言不是)满足$xcal A ⁇ r(($cal X})\subset_cal A ⁇ r($cal X})$。缺乏单色性可能会在使用阿尔法综合体时带来巨大的计算成本,有时甚至使其无法使用。在这项工作中,我们提出了一个基于阿尔法综合体的新构造,在保持单一性的同时,它与阿尔法综合体等同。我们提供了构建这个综合体所需的正式定义和算法。此外,我们分析这个综合体的大小,以证明它的使用成本不会比标准的阿尔法综合体要高得多。
相关内容
微信扫码咨询专知VIP会员