Document Open Access Logo

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions d ≥ 4

Authors Egor Gorbachev, Marvin Künnemann

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.36.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Author Details

Egor Gorbachev
  • Saarbrücken Graduate School of Computer Science, Saarland Informatics Campus, Saarbrücken, Germany
Marvin Künnemann
  • RPTU Kaiserslautern-Landau, Germany

Acknowledgements

The second author thanks Karl Bringmann, Nick Fischer and Karol Węgrzycki for helpful discussions.

Cite As Get BibTex

Egor Gorbachev and Marvin Künnemann. Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions d ≥ 4. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.36

Abstract

Klee’s measure problem (computing the volume of the union of n axis-parallel boxes in ℝ^d) is well known to have n^{d/2± o(1)}-time algorithms (Overmars, Yap, SICOMP'91; Chan FOCS'13). Only recently, a conditional lower bound (without any restriction to "combinatorial" algorithms) could be shown for d = 3 (Künnemann, FOCS'22). Can this result be extended to a tight lower bound for dimensions d ≥ 4?
In this paper, we formalize the technique of the tight lower bound for d = 3 using a combinatorial object we call prefix covering design. We show that these designs, which are related in spirit to combinatorial designs, directly translate to conditional lower bounds for Klee’s measure problem and various related problems. By devising good prefix covering designs, we give the following lower bounds for Klee’s measure problem in ℝ^d, the depth problem for axis-parallel boxes in ℝ^d, the largest-volume/max-perimeter empty (anchored) box problem in ℝ^{2d}, and related problems:  
- Ω(n^1.90476) for d = 4, 
- Ω(n^2.22222) for d = 5, 
- Ω(n^{d/3 + 2√d/9-o(√d)}) for general d,  assuming the 3-uniform hyperclique hypothesis. For Klee’s measure problem and the depth problem, these bounds improve previous lower bounds of Ω(n^{1.777...}), Ω(n^{2.0833...}) and Ω(n^{d/3 + 1/3 + Θ(1/d)}) respectively.
Our improved prefix covering designs were obtained by (1) exploiting a computer-aided search using problem-specific insights as well as SAT solvers, and (2) showing how to transform combinatorial covering designs known in the literature to strong prefix covering designs. In contrast, we show that our lower bounds are close to best possible using this proof technique.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Fine-grained complexity theory
  • non-combinatorial lower bounds
  • computational geometry
  • clique detection

Metrics

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

Related Versions

References

  1. Pankaj K. Agarwal. An improved algorithm for computing the volume of the union of cubes. In David G. Kirkpatrick and Joseph S. B. Mitchell, editors, Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010, pages 230-239. ACM, 2010. URL: https://doi.org/10.1145/1810959.1811000.
  2. Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir. Computing the volume of the union of cubes. In Jeff Erickson, editor, Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, pages 294-301. ACM, 2007. URL: https://doi.org/10.1145/1247069.1247121.
  3. Alok Aggarwal and Subhash Suri. Fast algorithms for computing the largest empty rectangle. In D. Soule, editor, Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, pages 278-290. ACM, 1987. URL: https://doi.org/10.1145/41958.41988.
  4. Jonathan Backer and J. Mark Keil. The mono- and bichromatic empty rectangle and square problems in all dimensions. In Alejandro López-Ortiz, editor, LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, volume 6034 of Lecture Notes in Computer Science, pages 14-25. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-12200-2_3.
  5. Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight hardness results for maximum weight rectangles. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 81:1-81:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.81.
  6. Jérémy Barbay, Timothy M. Chan, Gonzalo Navarro, and Pablo Pérez-Lantero. Maximum-weight planar boxes in o(n²) time (and better). Inf. Process. Lett., 114(8):437-445, 2014. URL: https://doi.org/10.1016/j.ipl.2014.03.007.
  7. J. L. Bentley. Algorithms for Klee’s rectangle problems. Department of Computer Science, Carnegie Mellon University, Unpublished notes, 1977. Google Scholar
  8. Nicola Beume, Carlos M. Fonseca, Manuel López-Ibáñez, Luís Paquete, and Jan Vahrenhold. On the complexity of computing the hypervolume indicator. IEEE Trans. Evol. Comput., 13(5):1075-1082, 2009. URL: https://doi.org/10.1109/TEVC.2009.2015575.
  9. Karl Bringmann. An improved algorithm for Klee’s measure problem on fat boxes. Comput. Geom., 45(5-6):225-233, 2012. URL: https://doi.org/10.1016/j.comgeo.2011.12.001.
  10. Karl Bringmann. Bringing order to special cases of Klee’s measure problem. In Krishnendu Chatterjee and Jirí Sgall, editors, Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, volume 8087 of Lecture Notes in Computer Science, pages 207-218. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40313-2_20.
  11. Karl Bringmann and Marvin Künnemann. Improved approximation for fréchet distance on c-packed curves matching conditional lower bounds. Int. J. Comput. Geom. Appl., 27(1-2):85-120, 2017. URL: https://doi.org/10.1142/S0218195917600056.
  12. Timothy M. Chan. A (slightly) faster algorithm for Klee’s measure problem. Comput. Geom., 43(3):243-250, 2010. URL: https://doi.org/10.1016/j.comgeo.2009.01.007.
  13. Timothy M. Chan. Klee’s measure problem made easy. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 410-419. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.51.
  14. Timothy M. Chan. Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back. Discret. Comput. Geom., 61(4):899-922, 2019. URL: https://doi.org/10.1007/s00454-019-00062-5.
  15. Timothy M. Chan. Faster algorithms for largest empty rectangles and boxes. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference), volume 189 of LIPIcs, pages 24:1-24:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.24.
  16. Bernard Chazelle, Robert L. (Scot) Drysdale III, and D. T. Lee. Computing the largest empty rectangle. SIAM J. Comput., 15(1):300-315, 1986. URL: https://doi.org/10.1137/0215022.
  17. David P. Dobkin, David Eppstein, and Don P. Mitchell. Computing the discrepancy with applications to supersampling patterns. ACM Trans. Graph., 15(4):354-376, 1996. URL: https://doi.org/10.1145/234535.234536.
  18. Adrian Dumitrescu and Minghui Jiang. On the largest empty axis-parallel box amidst n points. Algorithmica, 66(2):225-248, 2013. URL: https://doi.org/10.1007/s00453-012-9635-5.
  19. Michael L. Fredman and Bruce W. Weide. On the complexity of computing the measure of u[ai, bi]. Commun. ACM, 21(7):540-544, 1978. URL: https://doi.org/10.1145/359545.359553.
  20. Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner. Hardness of discrepancy computation and ε-net verification in high dimension. J. Complex., 28(2):162-176, 2012. URL: https://doi.org/10.1016/j.jco.2011.09.001.
  21. Egor Gorbachev and Marvin Künnemann. Codes and constructions for Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions d ≥ 4. URL: https://github.com/Peltorator/klees-measure-lower-bounds-repo.
  22. Egor Gorbachev and Marvin Künnemann. Combinatorial designs meet hypercliques: Higher lower bounds for Klee’s measure problem and related problems in dimensions d ≥ 4, 2023. URL: https://doi.org/10.48550/ARXIV.2303.08612.
  23. Daniel M. Gordon. La jolla covering repository. https://www.dmgordon.org/cover/. Accessed: 2022-11-27.
  24. Daniel M. Gordon, Greg Kuperberg, and Oren Patashnik. New constructions for covering designs. Journal of Combinatorial Designs, 3:269-284, 1995. Google Scholar
  25. Daniel M. Gordon and Douglas R. Stinson. Coverings. In Charles J. Colbourn and Jeffrey H. Dinitz, editors, Handbook of Combinatorial Designs. Chapman and Hall, 2006. Google Scholar
  26. Victor Klee. Can the measure of ⋃₁ⁿ[a_i,b_i] be computed in less than O(nlog n) steps? The American Mathematical Monthly, 84(4):284-285, 1977. Google Scholar
  27. Marvin Künnemann. A tight (non-combinatorial) conditional lower bound for Klee’s measure problem in 3d. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 555-566. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00059.
  28. W. Mantel. Problem 28: Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff. In Wiskundige Opgaven 10, pages 60-61. W. Mantel, 1907. Google Scholar
  29. W. H. Mills and R. C. Mullin. Coverings and packings. In J. H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory: A Collection of Surveys, pages 371-399. Wiley, 1992. Google Scholar
  30. Amnon Naamad, D. T. Lee, and Wen-Lian Hsu. On the maximum empty rectangle problem. Discret. Appl. Math., 8(3):267-277, 1984. URL: https://doi.org/10.1016/0166-218X(84)90124-0.
  31. Mark H. Overmars and Chee-Keng Yap. New upper bounds in Klee’s measure problem. SIAM J. Comput., 20(6):1034-1045, 1991. URL: https://doi.org/10.1137/0220065.
  32. Jan van Leeuwen and Derick Wood. The measure problem for rectangular ranges in d-space. J. Algorithms, 2(3):282-300, 1981. URL: https://doi.org/10.1016/0196-6774(81)90027-4.
  33. Hakan Yildiz and Subhash Suri. On klee’s measure problem for grounded boxes. In Tamal K. Dey and Sue Whitesides, editors, Proceedings of the 28th ACM Symposium on Computational Geometry, Chapel Hill, NC, USA, June 17-20, 2012, pages 111-120. ACM, 2012. URL: https://doi.org/10.1145/2261250.2261267.
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 About DROPS Imprint Privacy Contact