论文标题
一种简单且最佳的算法，用于严格的循环序列
A simple and optimal algorithm for strict circular seriation
论文作者
论文摘要
最近，阿姆斯特朗（Armstrong），古兹曼（Guzmán）和Sing Long（2021）提出了一种最佳的$ O（N^2）$ time算法，用于严格的圆形序列（也称为严格的准圆形鲁滨逊空间）。在本文中，我们给出了一个非常简单的$ O（n \ log n）$ time算法，用于计算严格的圆形串行的兼容循环顺序。当不知道输入空间是严格的准圆形鲁滨逊时，我们的算法会得到$ O（n^2）$ $ o（n^2）$时间验证返回订单的时间验证。该算法还可以识别文献中已知的其他类型的严格的圆形鲁滨逊空间。我们还证明，圆形的鲁滨逊差异（通过在每对点之间的两个弧线之一上存在兼容订单来定义）恰好是前圆形鲁滨逊差异（由四点条件定义）。
Recently, Armstrong, Guzmán, and Sing Long (2021), presented an optimal $O(n^2)$ time algorithm for strict circular seriation (called also the recognition of strict quasi-circular Robinson spaces). In this paper, we give a very simple $O(n\log n)$ time algorithm for computing a compatible circular order for strict circular seriation. When the input space is not known to be strict quasi-circular Robinson, our algorithm is complemented by an $O(n^2)$ time verification of compatibility of the returned order. This algorithm also works for recognition of other types of strict circular Robinson spaces known in the literature. We also prove that the circular Robinson dissimilarities (which are defined by the existence of compatible orders on one of the two arcs between each pair of points) are exactly the pre-circular Robinson dissimilarities (which are defined by a four-point condition).
