### 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.

Original language | English (US) |
---|---|

Title of host publication | Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 160-171 |

Number of pages | 12 |

ISBN (Print) | 3540388753, 9783540388753 |

DOIs | |

State | Published - 2006 |

Event | 14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland Duration: Sep 11 2006 → Sep 13 2006 |

### Publication series

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

Volume | 4168 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 14th Annual European Symposium on Algorithms, ESA 2006 |
---|---|

Country | Switzerland |

City | Zurich |

Period | 9/11/06 → 9/13/06 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

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

## Cite this

*Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings*(pp. 160-171). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4168 LNCS). Springer Verlag. https://doi.org/10.1007/11841036_17