Necklaces, Convolutions, and X+Y
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 ℓ [subscript p] norm of the vector of distances between pairs of beads from opposite...
Main Authors: | Bremner, David, Chan, Timothy M., Demaine, Erik D., Erickson, Jeff, Hurtado, Ferran, Iacono, John, Langerman, Stefan, Patrascu, Mihai, Taslakian, Perouz |
---|---|
Other Authors: | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
Format: | Article |
Language: | en_US |
Published: |
Springer-Verlag
2015
|
Online Access: | http://hdl.handle.net/1721.1/99983 https://orcid.org/0000-0003-3803-5703 |
Similar Items
-
Necklaces, Convolutions, and X+Y
by: Bremner, David, et al.
Published: (2019) -
Coloring and Guarding Arrangements
by: Prosenjit Bose, et al.
Published: (2013-12-01) -
Non-crossing matchings of points with geometric objects
by: Aloupis, Greg, et al.
Published: (2015) -
Matching Points with Things
by: Aloupis, Greg, et al.
Published: (2012) -
Worst-Case Optimal Tree Layout in External Memory
by: Demaine, Erik D., et al.
Published: (2014)