Paper by Erik D. Demaine

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian, “Necklaces, Convolutions, and X + Y”, in Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), Zürich, Switzerland, September 11–13, 2006, pages 160–171.

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 ℓ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(n2) time, whereas the obvious algorithms for these problems run in Θ(n2) time.

This paper is also available from SpringerLink.

Copyright held by the authors.

The paper is available in PostScript (1290k) and PDF (254k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 21, 2017 by Erik Demaine.