Abstract
Klee’s measure problem (computing the volume of the union of n axisparallel 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 axisparallel boxes in ℝ^d, the largestvolume/maxperimeter 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/9o(√d)}) for general d, assuming the 3uniform 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 computeraided search using problemspecific 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.
BibTeX  Entry
@InProceedings{gorbachev_et_al:LIPIcs.SoCG.2023.36,
author = {Gorbachev, Egor and K\"{u}nnemann, Marvin},
title = {{Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions d ≥ 4}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {36:136:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17886},
URN = {urn:nbn:de:0030drops178861},
doi = {10.4230/LIPIcs.SoCG.2023.36},
annote = {Keywords: Finegrained complexity theory, noncombinatorial lower bounds, computational geometry, clique detection}
}
Keywords: 

Finegrained complexity theory, noncombinatorial lower bounds, computational geometry, clique detection 
Collection: 

39th International Symposium on Computational Geometry (SoCG 2023) 
Issue Date: 

2023 
Date of publication: 

09.06.2023 