## Necklaces, convolutions, and X+Y

Written with
David Bremner,
Timothy M. Chan,
Erik D. Demaine,
Ferran Hurtado,
John Iacono,
Stefan Langerman,
Mihai Pătraşcu, and
Perouz Taslakian*.
Algorithmica 69(2):294–314, 2014.

Preliminary version (without Mihai's contributions) in
Proceedings of the 12th Annual European Symposium on Algorithms, 160-171, 2006.

- Download revised journal submission:
- Download ESA version:

**Abstract:**

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=∞. For p=2, we reduce the problem to standard convolution, while for p=∞ 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 Θ(n^{2}) time.

Publications -
Jeff Erickson
(jeffe@cs.uiuc.edu)
14 Octo 2014