Document Open Access Logo

Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation

Authors Karl Bringmann, André Nusser

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.18.pdf
  • Filesize: 0.89 MB
  • 17 pages

Document Identifiers

Author Details

Karl Bringmann
  • Universität des Saarlandes, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
André Nusser
  • Saarbrücken Graduate School of Computer Science, Universität des Saarlandes, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Funding

  • Bringmann, Karl: This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979).

Cite AsGet BibTex

Karl Bringmann and André Nusser. Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.18

Abstract

Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible. Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size n and m, the Hausdorff distance under translation can be computed in time 𝒪̃(nm) for the L₁ and L_∞ norm [Chew, Kedem SWAT'92] and 𝒪̃(nm (n+m)) for the L₂ norm [Huttenlocher, Kedem, Sharir DCG'93]. As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of (nm)^{1-o(1)} for L₁ and L_∞ assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of n^{2-o(1)} for L₂ in the imbalanced case of m = 𝒪(1) assuming the 3SUM Hypothesis.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Hausdorff Distance Under Translation
  • Fine-Grained Complexity Theory
  • Lower Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 192-203. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.26.
  2. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 39-51. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_4.
  3. Helmut Alt and Michael Godau. Computing the Fréchet Distance between Two Polygonal Curves. Int. J. Comput. Geometry Appl., 5:75-91, 1995. URL: https://doi.org/10.1142/S0218195995000064.
  4. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 114-125. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_10.
  5. Chanderjit Bajaj. The algebraic degree of geometric optimization problems. Discrete & Computational Geometry, 3(2):177-191, 1988. Google Scholar
  6. Gill Barequet and Sariel Har-Peled. Polygon containment and translational in-hausdorff-distance between segment sets are 3sum-hard. International Journal of Computational Geometry & Applications, 11(04):465-474, 2001. URL: https://doi.org/10.1142/S0218195901000596.
  7. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 661-670. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.76.
  8. Karl Bringmann and Marvin Künnemann. Multivariate fine-grained complexity of longest common subsequence. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1216-1235. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.79.
  9. Karl Bringmann, Marvin Künnemann, and André Nusser. Fréchet distance under translation: Conditional hardness and an algorithm via offline dynamic grid reachability. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2902-2921. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.180.
  10. Karl Bringmann, Marvin Künnemann, and André Nusser. When lipschitz walks your dog: Algorithm engineering of the discrete fréchet distance under translation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 25:1-25:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.25.
  11. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete fréchet distance. J. Comput. Geom., 7(2):46-76, 2016. URL: https://doi.org/10.20382/jocg.v7i2a4.
  12. Kevin Buchin, Anne Driemel, Natasja van de L'Isle, and André Nusser. klcluster: Center-based clustering of trajectories. In Farnoush Banaei Kashani, Goce Trajcevski, Ralf Hartmut Güting, Lars Kulik, and Shawn D. Newsam, editors, Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2019, Chicago, IL, USA, November 5-8, 2019, pages 496-499. ACM, 2019. URL: https://doi.org/10.1145/3347146.3359111.
  13. Kevin Buchin, Tim Ophelders, and Bettina Speckmann. SETH says: Weak fréchet distance is faster, but only if it is continuous and in one dimension. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2887-2901. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.179.
  14. Timothy M. Chan and Qizheng He. Reducing 3sum to convolution-3sum. In Martin Farach-Colton and Inge Li Gørtz, editors, 3rd Symposium on Simplicity in Algorithms, SOSA@SODA 2020, Salt Lake City, UT, USA, January 6-7, 2020, pages 1-7. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976014.1.
  15. L. P. Chew, D. Dor, A. Efrat, and K. Kedem. Geometric pattern matching in d-dimensional space. Discrete & Computational Geometry, 21(2):257-274, February 1999. URL: https://doi.org/10.1007/PL00009420.
  16. L. Paul Chew and Klara Kedem. Improvements on geometric pattern matching problems. In Otto Nurmi and Esko Ukkonen, editors, Algorithm Theory — SWAT '92, Lecture Notes in Computer Science, pages 318-325. Springer Berlin Heidelberg, 1992. Google Scholar
  17. Mark de Berg, Atlas F. Cook, and Joachim Gudmundsson. Fast fréchet queries. Computational Geometry, 46(6):747-755, 2013. URL: https://doi.org/10.1016/j.comgeo.2012.11.006.
  18. A. Efrat, A. Itai, and M. J. Katz. Geometry Helps in Bottleneck Matching and Related Problems. Algorithmica, 31(1):1-28, 2001. URL: https://doi.org/10.1007/s00453-001-0016-8.
  19. Andriy Fedorov, Eric Billet, Marcel Prastawa, Guido Gerig, Alireza Radmanesh, Simon K Warfield, Ron Kikinis, and Nikos Chrisochoides. Evaluation of brain mri alignment with the robust hausdorff distance measures. In International Symposium on Visual Computing, pages 594-603. Springer, 2008. Google Scholar
  20. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. URL: https://doi.org/10.1016/0925-7721(95)00022-2.
  21. Felix Hausdorff. Grundzüge der Mengenlehre, volume 7. von Veit, 1914. Google Scholar
  22. Daniel P Huttenlocher, Klara Kedem, and Micha Sharir. The upper envelope of voronoi surfaces and its applications. Discrete & Computational Geometry, 9(3):267-291, 1993. Google Scholar
  23. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  24. James King. A survey of 3sum-hard problems, 2004. Google Scholar
  25. Meinard Müller. Information retrieval for music and motion. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74048-3.
  26. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC '10, page 603–610, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1806689.1806772.
  27. Günter Rote. Computing the minimum Hausdorff distance between two point sets on a line under translation. Information Processing Letters, 38(3):123-127, 1991. URL: https://doi.org/10.1016/0020-0190(91)90233-8.
  28. W. J. Rucklidge. Lower bounds for the complexity of the graph of the Hausdorff distance as a function of transformation. Discrete & Computational Geometry, 16(2):135-153, 1996. URL: https://doi.org/10.1007/BF02716804.
  29. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proc. ICM, volume 3, pages 3431-3472. World Scientific, 2018. Google Scholar
  30. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact