Necklaces, convolutions, and X+Y
Necklaces, convolutions, and X+Y
复制标题
DOI：
10.1007/s00453-012-9734-3
复制
发表时间：
2006-01-01
期刊：
影响因子：
--
通讯作者：
Taslakian, Perouz
中科院分区：
文献类型：
--
作者：
Bremner, David;Chan, Timothy M.;Taslakian, Perouz
我们给出了次二次算法，给定两条项链，每条项链在任意位置都有 n 个珠子，计算项链的最佳旋转以最好地对齐珠子。这里，对齐是根据最佳完美匹配中相对项链的成对珠子之间距离向量的 l(p) 范数来测量的。我们在 p = 1、p = 2 和 p = 无穷大时显示出令人惊讶的不同结果。对于 p = 2，我们将问题简化为标准卷积，而对于 p = 无穷大和 p = 1，我们将问题简化为 (min, +) 卷积和 (median, +) 卷积。然后我们在次二次时间内解决了后两个卷积问题，这本身就是有趣的结果。这些结果为经典排序 X + Y 问题提供了一些启示，因为卷积可以被视为计算 X + Y 矩阵反对角线上的阶统计量。我们所有的算法都在 o(n(2)) 时间内运行，而这些问题的明显算法在 Theta(n(2)) 时间内运行。
We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the l(p) norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p = 1, p = 2, and p = infinity. For p = 2, we reduce the problem to standard convolution, while for p = infinity and p = 1, we reduce the problem to (min, +) convolution and (median, +) convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X + Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X + Y matrix. All of our algorithms run in o(n(2)) time, whereas the obvious algorithms for these problems run in Theta(n(2)) time.