Necklaces, convolutions, and X + Y

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publicationAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
    PublisherSpringer Verlag
    Number of pages12
    ISBN (Print)3540388753, 9783540388753
    StatePublished - 2006
    Event14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland
    Duration: Sep 11 2006Sep 13 2006

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume4168 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other14th Annual European Symposium on Algorithms, ESA 2006

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


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

    Cite this