Document Open Access Logo

Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem

Author Timothy M. Chan

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.24.pdf
  • Filesize: 0.73 MB
  • 13 pages

Document Identifiers

Author Details

Timothy M. Chan
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA

Funding

  • Chan, Timothy M.: Work supported in part by NSF Grant CCF-2224271.

Cite AsGet BibTex

Timothy M. Chan. Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.24

Abstract

We present a (combinatorial) algorithm with running time close to O(n^d) for computing the minimum directed L_∞ Hausdorff distance between two sets of n points under translations in any constant dimension d. This substantially improves the best previous time bound near O(n^{5d/4}) by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new generalization of Chan’s algorithm [FOCS'13] for Klee’s measure problem. To complement this algorithmic result, we also prove a nearly matching conditional lower bound close to Ω(n^d) for combinatorial algorithms, under the Combinatorial k-Clique Hypothesis.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Hausdorff distance
  • geometric optimization
  • Klee’s measure problem
  • fine-grained complexity

Metrics

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

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. SIAM J. Comput., 47(6):2527-2555, 2018. Preliminary version in FOCS 2015. URL: https://doi.org/10.1137/16M1061771.
  2. Pankaj K. Agarwal. An improved algorithm for computing the volume of the union of cubes. In Proc. 26th ACM Symposium on Computational Geometry (SoCG), pages 230-239, 2010. URL: https://doi.org/10.1145/1810959.1811000.
  3. Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, and Yusu Wang. Hausdorff distance under translation for points and balls. ACM Trans. Algorithms, 6(4):71:1-71:26, 2010. Preliminary version in SoCG 2003. URL: https://doi.org/10.1145/1824777.1824791.
  4. Oswin Aichholzer, Helmut Alt, and Günter Rote. Matching shapes with a reference point. Int. J. Comput. Geom. Appl., 7(4):349-363, 1997. Preliminary version in SoCG 1994. URL: https://doi.org/10.1142/S0218195997000211.
  5. Boris Aronov and Jean Cardinal. Geometric pattern matching reduces to k-SUM. In Proc. 31st International Symposium on Algorithms and Computation (ISAAC), volume 181, pages 32:1-32:9, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.32.
  6. Gill Barequet and Sariel Har-Peled. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard. Int. J. Comput. Geom. Appl., 11(4):465-474, 2001. URL: https://doi.org/10.1142/S0218195901000596.
  7. Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. In Proc. 11th Annual Symposium on Computational Geometry (SoCG), pages 79-88, 1995. URL: https://doi.org/10.1145/220279.220288.
  8. Karl Bringmann. An improved algorithm for Klee’s measure problem on fat boxes. Comput. Geom., 45(5-6):225-233, 2012. Preliminary version in SoCG 2010. URL: https://doi.org/10.1016/j.comgeo.2011.12.001.
  9. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 307-318, 2017. URL: https://doi.org/10.1109/FOCS.2017.36.
  10. Karl Bringmann and André Nusser. Translating Hausdorff is hard: Fine-grained lower bounds for Hausdorff distance under translation. In Proc. 37th International Symposium on Computational Geometry (SoCG), pages 18:1-18:17, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.18.
  11. Sergio Cabello, Panos Giannopoulos, and Christian Knauer. On the parameterized complexity of d-dimensional point set pattern matching. Inf. Process. Lett., 105(2):73-77, 2008. URL: https://doi.org/10.1016/j.ipl.2007.08.003.
  12. Timothy M. Chan. Geometric applications of a randomized optimization technique. Discret. Comput. Geom., 22(4):547-567, 1999. Preliminary version in SoCG 1998. URL: https://doi.org/10.1007/PL00009478.
  13. Timothy M. Chan. A (slightly) faster algorithm for Klee’s measure problem. Comput. Geom., 43(3):243-250, 2010. Preliminary version in SoCG 2008. URL: https://doi.org/10.1016/j.comgeo.2009.01.007.
  14. Timothy M. Chan. Klee’s measure problem made easy. In Proc. 54th IEEE Symposium on Foundations of Computer Science (FOCS), pages 410-419, 2013. URL: https://doi.org/10.1109/FOCS.2013.51.
  15. L. Paul Chew, Dorit Dor, Alon Efrat, and Klara Kedem. Geometric pattern matching in d-dimensional space. Discret. Comput. Geom., 21(2):257-274, 1999. Preliminary version in ESA 1995. URL: https://doi.org/10.1007/PL00009420.
  16. L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, and Dina Kravets. Geometric pattern matching under Euclidean motion. Comput. Geom., 7:113-124, 1997. URL: https://doi.org/10.1016/0925-7721(95)00047-X.
  17. L. Paul Chew and Klara Kedem. Getting around a lower bound for the minimum Hausdorff distance. Comput. Geom., 10(3):197-202, 1998. Preliminary version in SWAT 1992. URL: https://doi.org/10.1016/S0925-7721(97)00032-1.
  18. Minkyoung Cho and David M. Mount. Improved approximation bounds for planar point pattern matching. Algorithmica, 50(2):175-207, 2008. URL: https://doi.org/10.1007/s00453-007-9059-9.
  19. Alon Efrat, Piotr Indyk, and Suresh Venkatasubramanian. Pattern matching for sets of segments. Algorithmica, 40(3):147-160, 2004. Preliminary version in SODA 2001. URL: https://doi.org/10.1007/s00453-004-1089-y.
  20. Greg N. Frederickson and Donald B. Johnson. Generalized selection and ranking: Sorted matrices. SIAM J. Comput., 13(1):14-30, 1984. URL: https://doi.org/10.1137/0213002.
  21. Michael T. Goodrich, Joseph S. B. Mitchell, and Mark W. Orletsky. Approximate geometric pattern matching under rigid motions. IEEE Trans. Pattern Anal. Mach. Intell., 21(4):371-379, 1999. Preliminary version in SoCG 1994. URL: https://doi.org/10.1109/34.761267.
  22. Daniel P. Huttenlocher and Klara Kedem. Computing the minimum Hausdorff distance for point sets under translation. In Proc. 6th ACM Symposium on Computational Geometry (SoCG), pages 340-349, 1990. URL: https://doi.org/10.1145/98524.98599.
  23. Daniel P. Huttenlocher, Klara Kedem, and Micha Sharir. The upper envelope of Voronoi surfaces and its applications. Discret. Comput. Geom., 9:267-291, 1993. Preliminary version in SoCG 1991. URL: https://doi.org/10.1007/BF02189323.
  24. Piotr Indyk, Rajeev Motwani, and Suresh Venkatasubramanian. Geometric matching under noise: Combinatorial bounds and algorithms. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 457-465, 1999. URL: http://dl.acm.org/citation.cfm?id=314500.314601.
  25. Ce Jin and Yinzhan Xu. Tight dynamic problem lower bounds from generalized BMM and OMv. In Proc. 54th Annual ACM Symposium on Theory of Computing (STOC), pages 1515-1528, 2022. URL: https://doi.org/10.1145/3519935.3520036.
  26. Marvin Künnemann. A tight (non-combinatorial) conditional lower bound for Klee’s Measure Problem in 3D. In Proc. 63rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 555-566, 2022. Google Scholar
  27. André Nusser. Fine-Grained Complexity and Algorithm Engineering of Geometric Similarity Measures. PhD thesis, Saarland University, Saarbrücken, Germany, 2021. URL: https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/33904.
  28. Mark H. Overmars and Chee-Keng Yap. New upper bounds in Klee’s measure problem. SIAM J. Comput., 20(6):1034-1045, 1991. Preliminary version in FOCS 1988. URL: https://doi.org/10.1137/0220065.
  29. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, volume 3, pages 3431-3472. World Scientific, 2018. URL: https://people.csail.mit.edu/virgi/eccentri.pdf.
  30. Hakan Yildiz and Subhash Suri. Computing Klee’s measure of grounded boxes. Algorithmica, 71(2):307-329, 2015. Preliminary version in SoCG 2012. URL: https://doi.org/10.1007/s00453-013-9797-9.
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