Necklaces, convolutions, and X+Y

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Pǎtraşcu, Perouz Taslakian

    Research output: Contribution to journalArticle

    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 even, and p=∞. For p even, 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.

    Original languageEnglish (US)
    Pages (from-to)294-314
    Number of pages21
    JournalAlgorithmica
    Volume69
    Issue number2
    DOIs
    StatePublished - Jun 2014

    Keywords

    • All pairs shortest paths
    • Convolution
    • Cyclic swap distance
    • Necklace alignment

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Necklaces, convolutions, and X+Y'. Together they form a unique fingerprint.

  • Cite this

    Bremner, D., Chan, T. M., Demaine, E. D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Pǎtraşcu, M., & Taslakian, P. (2014). Necklaces, convolutions, and X+Y. Algorithmica, 69(2), 294-314. https://doi.org/10.1007/s00453-012-9734-3