Document Open Access Logo

The Complexity of the Hausdorff Distance

Authors Paul Jungeblut , Linda Kleist , Tillmann Miltzow

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.48.pdf
  • Filesize: 1.36 MB
  • 17 pages

Document Identifiers

Author Details

Paul Jungeblut
  • Karlsruhe Institute of Technology, Germany
Linda Kleist
  • Technische Universität Braunschweig, Germany
Tillmann Miltzow
  • Utrecht University, The Netherlands

Funding

  • Kleist, Linda: Partially supported by a postdoc fellowship of the German Academic Exchange Service (DAAD).
  • Miltzow, Tillmann: Generously supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250.

Cite AsGet BibTex

Paul Jungeblut, Linda Kleist, and Tillmann Miltzow. The Complexity of the Hausdorff Distance. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.48

Abstract

We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algebraic sets is bounded by a given threshold is complete for the complexity class ∀∃_<ℝ. This implies that the problem is NP-, co-NP-, ∃ℝ- and ∀ℝ-hard.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Hausdorff Distance
  • Semi-Algebraic Set
  • Existential Theory of the Reals
  • Universal Existential Theory of the Reals
  • Complexity Theory

Metrics

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

Related Versions

References

  1. Zachary Abel, Erik Demaine, Martin Demaine, Sarah Eisenstat, Jayson Lynch, and Tao Schardl. Who Needs Crossings? Hardness of Plane Graph Rigidity. In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1-3:15, 2016. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.3.
  2. Mikkel Abrahamsen. Covering Polygons is Even Harder. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.02335.
  3. Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The Art Gallery Problem is ∃ℝ-complete. In STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 65-73, 2018. URL: https://doi.org/10.1145/3188745.3188868.
  4. Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Geometric Embeddability of Complexes is ∃ℝ-complete. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.02585.
  5. Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training Neural Networks is ER-complete. In Marc A. Ranzato, Alina Beygelzimer, K. Nguyen, Percy Liang, Jennifer W. Vaughan, and Yann Dauphin, editors, Advances in Neural Information Processing Systems (NeurIPS 2021), volume 34, 2021. Google Scholar
  6. Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. Framework for ER-Completeness of Two-Dimensional Packing Problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1014-1021, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00098.
  7. Helmut Alt, Bernd Behrends, and Johannes Blömer. Approximate Matching of Polygonal Shapes. Annals of Mathematics and Artificial Intelligence, 13(3):251-265, 1995. URL: https://doi.org/10.1007/BF01530830.
  8. Helmut Alt, Peter Braß, Michael Godau, Christian Knauer, and Carola Wenk. Computing the Hausdorff Distance of Geometric Patterns and Shapes. In Boris Aronov, Saugata Basu, János Pach, and Micha Sharir, editors, Discrete and Computational Geometry: The Goodman-Pollack Festschrift, volume 25 of Algorithms and Combinatorics, pages 65-76. Springer, 2003. URL: https://doi.org/10.1007/978-3-642-55566-4_4.
  9. Helmut Alt and Leonidas J. Guibas. Discrete Geometric Shapes: Matching, Interpolation, and Approximation. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 121-153. Elsevier, 2000. URL: https://doi.org/B978-044482537-7/50004-8.
  10. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. URL: https://doi.org/10.1017/CBO9780511804090.
  11. Mikhail J. Atallah. A Linear Time Algorithm for the Hausdorff Distance Between Convex Polygons. Information Processing Letters, 17(4):207-209, 1983. URL: https://doi.org/10.1016/0020-0190(83)90042-X.
  12. Sauguta Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics. Springer, 2006. URL: https://doi.org/10.1007/3-540-33099-2.
  13. Sauguta Basu and Marie-Françoise Roy. Bounding the radii of balls meeting every connected component of semi-algebraic sets. Journal of Symbolic Computation, 45(12):1270-1279, 2010. URL: https://doi.org/10.1016/j.jsc.2010.06.009.
  14. Maria Belk. Realizability of Graphs in Three Dimensions. Discrete & Computational Geometry, 37(2):139-162, 2007. URL: https://doi.org/10.1007/s00454-006-1285-4.
  15. Vittorio Bilò and Marios Mavronicolas. A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:13, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.17.
  16. Lenore Blum, Mike Shub, and Steve Smale. On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines. Bulletin of the American Mathematical Society, 21:1-46, 1989. URL: https://doi.org/10.1090/S0273-0979-1989-15750-9.
  17. Glen E. Bredon. Topology and Geometry, volume 139 of Graduate Texts in Mathematics. Springer Science & Business Media, 1st edition, 2013. URL: https://doi.org/10.1007/978-1-4757-6848-0.
  18. Karl Bringmann and André Nusser. Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1-18:17, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.18.
  19. Peter Bürgisser and Felipe Cucker. Exotic Quantifiers, Complexity Classes, and Complete Problems. Foundations of Computational Mathematics, 9(2):135-170, 2009. URL: https://doi.org/10.1007/s10208-007-9006-9.
  20. Jean Cardinal. Computational Geometry Column 62. ACM SIGACT News, 46(4):69-78, 2015. URL: https://doi.org/10.1145/2852040.2852053.
  21. Jean Cardinal and Udo Hoffmann. Recognition and Complexity of Point Visibility Graphs. Discrete & Computational Geometry, 57(1):164-178, 2017. URL: https://doi.org/10.1007/s00454-016-9831-1.
  22. Wiki Community. Homotopy. accessed 2021 November. URL: https://en.wikipedia.org/wiki/Homotopy.
  23. David Cox, John Little, and Donal O'Shea. Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics. Springer, 2nd edition, 2006. URL: https://doi.org/10.1007/b138611.
  24. James H. Davenport and Joos Heintz. Real Quantifier Elimination is Doubly Exponential. Journal of Symbolic Computation, 5(1-2):29-35, 1988. URL: https://doi.org/10.1016/S0747-7171(88)80004-X.
  25. Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrel. On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets. In Filippo Bonchi and Simon J. Puglisi, editors, International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:21, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.33.
  26. Michael G. Dobbins, Andreas Holmsen, and Tillmann Miltzow. A Universality Theorem for Nested Polytopes. arXiv preprint, 2019. URL: http://arxiv.org/abs/1908.02213.
  27. Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rzążewski. ∀∃ℝ-Completeness and Area-Universality. In Andreas Brandstädt, Ekkehard Köhler, and Klaus Meer, editors, Graph-Theoretic Concepts in Computer Science (WG), volume 11159 of Lecture Notes in Computer Science, pages 164-175. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-00256-5_14.
  28. Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rzążewski. Completeness for the Complexity Class ∀∃ℝ and Area-Universality. arXiv preprint, 2021. URL: http://arxiv.org/abs/1712.05142v3.
  29. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. ∃ℝ-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria. ACM Transactions on Economics and Computation, 6(1):1:1-1:23, 2018. URL: https://doi.org/10.1145/3175494.
  30. Michael Godau. On the complexity of measuring the similarity between geometric objects in higher dimensions. PhD thesis, Freie Universtät Berlin, 1999. URL: https://doi.org/10.17169/refubium-7780.
  31. Dmitrii Y. Grigor'ev and Nicolai N. Vorobjov. Solving Systems of Polynomial Inequalities in Subexponential Time. Journal of Symbolic Computation, 5(1-2):37-64, 1988. URL: https://doi.org/10.1016/S0747-7171(88)80005-1.
  32. Felix Hausdorff. Grundzüge der Mengenlehre. Von Veit & Company, 1914. Google Scholar
  33. Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal. The Complexity of Drawing a Graph in a Polygonal Region. In Therese Biedl and Andreas Kerren, editors, GD 2018: Graph Drawing and Network Visualization, volume 11282 of Lecture Notes in Computer Science, pages 387-401, 2018. URL: https://doi.org/10.1007/978-3-030-04414-5_28.
  34. Jiří Matoušek. Intersection graphs of segments and ∃ ℝ. arXiv preprint, 2014. URL: http://arxiv.org/abs/1406.2636.
  35. Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs. Journal of Combinatorial Theory, Series B, 103(1):114-143, 2013. URL: https://doi.org/10.1016/j.jctb.2012.09.004.
  36. Tillmann Miltzow and Reinier F. Schmiermann. On Classifying Continuous Constraint Satisfaction Problems. arXiv preprint, 2022. URL: http://arxiv.org/abs/2106.02397.
  37. Deng Min, Li Zhilin, and Chen Xiaoyong. Extended Hausdorff distance for spatial objects in GIS. International Journal of Geographical Information Science, 21(4):459-475, 2007. URL: https://doi.org/10.1080/13658810601073315.
  38. Nikolai E. Mnëv. The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytopes Varieties. In Oleg Y. Viro and Anatoly M Vershik, editors, Topology and Geometry — Rohlin Seminar, volume 1346 of Lecture Notes in Mathematics, pages 527-543. Springer, 1988. URL: https://doi.org/10.1007/BFb0082792.
  39. Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek. Polygon-Universal Graphs. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1-55:15, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.55.
  40. James Renegar. On the Computational Complexity and Geometry of the First-order Theory of the Reals. Part I: Introduction. Preliminaries. The Geometry of Semi-algebraic Sets. The Decision Problem for the Existential Theory of the Reals. Journal of Symbolic Computation, 13(3):255-299, 1992. URL: https://doi.org/10.1016/S0747-7171(10)80003-3.
  41. James Renegar. On the Computational Complexity and Geometry of the First-Order Theory of the Reals. Part II: The General Decision Problem. Preliminaries for Quantifier Elimination. Journal of Symbolic Computation, 13(3):301-327, 1992. URL: https://doi.org/10.1016/S0747-7171(10)80004-5.
  42. James Renegar. On the Computational Complexity and Geometry of the First-Order Theory of the Reals. Part III: Quantifier Elimination. Journal of Symbolic Computation, 13(3):329-352, 1992. URL: https://doi.org/10.1016/S0747-7171(10)80005-7.
  43. Jürgen Richter-Gebert and Günter M. Ziegler. Realization Spaces of 4-Polytopes are Universal. Bulletin of the American Mathematical Society, 32(4):403-412, 1995. URL: https://doi.org/10.1090/S0273-0979-1995-00604-X.
  44. Tim Roughgarden. Beyond Worst-Case Analysis. Communications of the ACM, 62(3):88-96, 2019. URL: https://doi.org/10.1145/3232535.
  45. William Rucklidge. Efficient Visual Recognition Using the Hausdorff Distance, volume 1173 of Lecture Notes in Computer Science. Springer, 1996. URL: https://doi.org/10.1007/BFb0015091.
  46. Marcus Schaefer. Complexity of Some Geometric and Topological Problems. In David Eppstein and Emden R. Gansner, editors, GD 2009: Graph Drawing, volume 5849 of Lecture Notes in Computer Science, pages 334-344, 2010. URL: https://doi.org/10.1007/978-3-642-11805-0_32.
  47. Marcus Schaefer. Realizability of Graphs and Linkages, pages 461-482. Thirty Essays on Geometric Graph Theory. Springer, 2013. URL: https://doi.org/10.1007/978-1-4614-0110-0_24.
  48. Marcus Schaefer and Daniel Štefankovič. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals. Theory of Computing Systems, 60:172-193, 2017. URL: https://doi.org/10.1007/s00224-015-9662-0.
  49. Yaroslav Shitov. A Universality Theorem for Nonnegative Matrix Factorizations. arXiv preprint, 2016. URL: http://arxiv.org/abs/1606.09068.
  50. Peter W. Shor. Stretchability of Pseudolines is NP-Hard. In Peter Gritzmann and Bernd Sturmfels, editors, Applied Geometry And Discrete Mathematics, volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 531-554, 1991. URL: https://doi.org/10.1090/dimacs/004/41.
  51. Daniel Spielman and Shang-Hua Teng. Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. Journal of the ACM, 51(3):385-463, 2004. URL: https://doi.org/10.1145/990308.990310.
  52. Floor Verhoeven, Amir Vaxman, Tim Hoffmann, and Olga Sorkine-Hornung. Dev2PQ: Planar Quadrilateral Strip Remeshing of Developable Surfaces. ACM Transactions on Graphics, 41(3):29:1-29:18, 2022. URL: https://doi.org/10.1145/3510002.
  53. Nicolai N. Vorob'ev. Estimates of Real Roots of a System of Algebraic Equations. Journal of Soviet Mathematics, 34:1754-1762, 1986. URL: https://doi.org/10.1007/BF01095637.
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