**Reference**:- 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. **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 ℓ_{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. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- Copyright held by the authors.
**Availability**:- 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.

Last updated October 28, 2020 by Erik Demaine.