Perouz Taslakian
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Perouz Taslakian has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- David Bremner
University of New Brunswick
2 shared publications - Erik D. Demaine
Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
2 shared publications - Fiama Pierina Orejuela Hurtado
Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya Barcelona Spain
2 shared publications - Jeff Erickson
University of Illinois Urbana-Champaign, Urbana, IL, USA
2 shared publications - Stefan Langerman
Computer Science Department Université Libre de Bruxelles Belgium
2 shared publications - Timothy M. Chan
David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada
2 shared publications
Latest Publications
- Open Access
- 28 December 2012
- Published by Springer Nature in Algorithmica
- Vol. 69 (2) , 294-314
Necklaces, Convolutions, and X+Y
- 28 December 2012
- Published by Springer Nature in Algorithmica
- Vol. 69 (2) , 294-314
Open AccessNecklaces, Convolutions, and X+Y
- Open Access
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 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 = \infty. For p even, we reduce the problem to standard convolution, while for p = \infty 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 \Theta(n^2) time.
Open AccessNecklaces, 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 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 = \infty. For p even, we reduce the problem to standard convolution, while for p = \infty 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 \Theta(n^2) time.