Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{Necklace_ESA2006,
  AUTHOR        = {David Bremner and Timothy M. Chan and Erik D. Demaine and
                   Jeff Erickson and Ferran Hurtado and John Iacono and
                   Stefan Langerman and Perouz Taslakian},
  TITLE         = {Necklaces, Convolutions, and {$X+Y$}},
  BOOKTITLE     = {Proceedings of the 14th Annual European Symposium on
                   Algorithms (ESA 2006)},
  bookurl       = {http://algo06.inf.ethz.ch/esa},
  ADDRESS       = {Z\"urich, Switzerland},
  MONTH         = {September 11--13},
  YEAR          = 2006,
  PAGES         = {160--171},

  copyright     = {Copyright held by the authors.},
  papers        = {Necklace_Algorithmica},
  doi           = {https://dx.doi.org/10.1007/11841036_17},
  dblp          = {https://dblp.org/rec/conf/esa/BremnerCDEHILT06},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/11841036_17">SpringerLink</A> and as <A HREF="https://arXiv.org/abs/1212.4771">arXiv:1212.4771</A>.},
}

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²) time, whereas the obvious algorithms for these problems run in Θ(n²) time.

Comments:

This paper is also available from SpringerLink and as arXiv:1212.4771.

Copyright:

Copyright held by the authors.

Availability:

The paper is available in PostScript (1290k) and PDF (254k).

See information on file formats.

[Google Scholar search]

Related papers:

Necklace_Algorithmica (Necklaces, Convolutions, and X + Y)