Back to Search Start Over

Necklaces, convolutions, and X plus Y

Authors :
Bremner, David
Chan, Timothy M.
Demaine, Erik D.
Erickson, Jeff
Hurtado Díaz, Fernando Alfredo
Iacono, John
Langerman, Stefan
Patrascu, Mihai
Taslakian, Perouz
Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
Source :
UPCommons. Portal del coneixement obert de la UPC, Universitat Politècnica de Catalunya (UPC), Recercat. Dipósit de la Recerca de Catalunya, Universitat Jaume I
Publication Year :
2014

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

Details

Language :
English
Database :
OpenAIRE
Journal :
UPCommons. Portal del coneixement obert de la UPC, Universitat Politècnica de Catalunya (UPC), Recercat. Dipósit de la Recerca de Catalunya, Universitat Jaume I
Accession number :
edsair.dedup.wf.001..112317bb92df637a23a6853f8cf70165