Search

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 ℓ 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 even, and p=∞. For p even, we reduce the problem to standard convolution, while for p=∞ and p=1, we reduce the problem to (min,+) convolution and $(\operatorname {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) time, whereas the obvious algorithms for these problems run in Θ( n) time. [ABSTRACT FROM AUTHOR]