论文标题
定期集合等轴测不变的渐近行为和接近线性的时间算法
The asymptotic behaviour and a near linear time algorithm for isometry invariants of periodic sets
论文作者
论文摘要
周期性结构的基本模型是设置为刚性运动或等轴测图的周期点。我们最近在SOCG 2021中定义的等轴测值（密度函数）的论文，在扰动下是一般且连续的。这项工作引入了更快的等轴测不变（平均最小距离），这也是连续的，并区分了具有相同密度函数的某些集合。我们明确描述了包括非周期性的各种套件的新不变式的渐近行为。所提出的近线性时间算法在几个小时内在适度的桌面上处理了数十万个真实结构的数据集。
The fundamental model of a periodic structure is a periodic point set up to rigid motion or isometry. Our recent paper in SoCG 2021 defined isometry invariants (density functions), which are complete in general position and continuous under perturbations. This work introduces much faster isometry invariants (average minimum distances), which are also continuous and distinguish some sets that have identical density functions. We explicitly describe the asymptotic behaviour of the new invariants for a wide class of sets including non-periodic. The proposed near linear time algorithm processed a dataset of hundreds of thousands of real structures in a few hours on a modest desktop.
