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
- 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
Last updated July 7, 2020 by