Four Soviets walk the dog, with an application to Alt's conjecture

K. Buchin, M. Buchin, W. Meulemans, W. Mulzer

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

34 Citaten (Scopus)
65 Downloads (Pure)

Samenvatting

Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One measure that is extremely popular is the Fréchet distance. Since it has been proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original O(n^2 log n) algorithm by Alt and Godau for computing the Fréchet distance remains the state of the art (here n denotes the number of vertices on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard.In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fréchet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fréchet distance between two polygonal curves in time O(n^2 \sqrt log n (log log n)^{3/2}) on a pointer machine and in time O(n^2 (log log n)^2) on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth O(n^{2¿}), for some ¿ > 0. This provides evidence that the decision problem may not be 3SUM-hard after all and reveals an intriguing new aspect of this well-studied problem.
Originele taal-2Engels
Titel25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
RedacteurenC. Chekuri
Plaats van productiePhiladelphia PA
UitgeverijSociety for Industrial and Applied Mathematics (SIAM)
Pagina's1399-1413
ISBN van geprinte versie978-1-61197-338-9
DOI's
StatusGepubliceerd - 2014
Evenement25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014) - Hilton Portland & Executive Tower, Portland, Verenigde Staten van Amerika
Duur: 5 jan 20147 jan 2014
Congresnummer: 25
https://www.siam.org/meetings/da14/

Congres

Congres25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
Verkorte titelSODA '14
LandVerenigde Staten van Amerika
StadPortland
Periode5/01/147/01/14
Ander25th Annual ACM-SIAM Symposium on Discrete Algorithms
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Four Soviets walk the dog, with an application to Alt's conjecture'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Buchin, K., Buchin, M., Meulemans, W., & Mulzer, W. (2014). Four Soviets walk the dog, with an application to Alt's conjecture. In C. Chekuri (editor), 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (blz. 1399-1413). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611973402.103