## 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 language | English (US) |
---|---|

Pages (from-to) | 294-314 |

Number of pages | 21 |

Journal | Algorithmica |

Volume | 69 |

Issue number | 2 |

DOIs | |

State | Published - 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