TY - GEN

T1 - Necklaces, convolutions, and X + Y

AU - Bremner, David

AU - Chan, Timothy M.

AU - Demaine, Erik D.

AU - Erickson, Jeff

AU - Hurtado, Ferran

AU - Iacono, John

AU - Langerman, Stefan

AU - Taslakian, Perouz

PY - 2006

Y1 - 2006

N2 - 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 ⊖(n2) time.

AB - 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 ⊖(n2) time.

UR - http://www.scopus.com/inward/record.url?scp=33750724735&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750724735&partnerID=8YFLogxK

U2 - 10.1007/11841036_17

DO - 10.1007/11841036_17

M3 - Conference contribution

AN - SCOPUS:33750724735

SN - 3540388753

SN - 9783540388753

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 160

EP - 171

BT - Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 14th Annual European Symposium on Algorithms, ESA 2006

Y2 - 11 September 2006 through 13 September 2006

ER -