Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Necklaces, convolutions, and X plus Y

Autor
Bremner, D.; Chan, T.; Demaine, E.; Erickson, J.; Hurtado, F.; Iacono, J.; Langerman, S.; Patrascu, M.; Taslakian, P.
Tipus d'activitat
Article en revista
Revista
Algorithmica
Data de publicació
2014-06-01
Volum
69
Número
2
Pàgina inicial
294
Pàgina final
314
DOI
https://doi.org/10.1007/s00453-012-9734-3 Obrir en finestra nova
Projecte finançador
Geometría Discreta: Problemas de Combinatoria y Computación
PROBLEMAS DE COMBINATORIA Y DE COMPUTACION
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
Repositori
http://hdl.handle.net/2117/24887 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007/s00453-012-9734-3 Obrir en finestra nova
Resum
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 a"" (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=a. For p even, we reduce the problem to standard convolution, while for p=a and p=1, we reduce the problem...
Citació
Bremner, D. [et al.]. Necklaces, convolutions, and X plus Y. "Algorithmica", 01 Juny 2014, vol. 69, núm. 2, p. 294-314.
Paraules clau
Necklace Alignment, Cyclic Swap Distance, Convolution, Sorting X Plus Y, All Pairs Shortest Paths, Pairs Shortest Paths, Dont Cares, Algorithms, Similarity, Transform
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Bremner, David  (autor)
  • Chan, Timothy M.  (autor)
  • Demaine, Erik D.  (autor)
  • Erickson, Jeff  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Iacono, John  (autor)
  • Langerman, Stefan  (autor)
  • Patrascu, Mihai  (autor)
  • Taslakian, Perouz  (autor)