English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Klee's measure problem (computing the volume of the union of $n$axis-parallel boxes in $\mathbb{R}^d$) is well known to have $n^{\frac{d}{2}\pmo(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\"unnemann, FOCS'22). Can this result beextended to a tight lower bound for dimensions $d\ge 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 thesedesigns, which are related in spirit to combinatorial designs, directlytranslate to conditional lower bounds for Klee's measure problem and variousrelated problems. By devising good prefix covering designs, we give thefollowing lower bounds for Klee's measure problem in $\mathbb{R}^d$, the depthproblem for axis-parallel boxes in $\mathbb{R}^d$, thelargest-volume/max-perimeter empty (anchored) box problem in $\mathbb{R}^{2d}$,and related problems:  - $\Omega(n^{1.90476})$ for $d=4$,  - $\Omega(n^{2.})$ for $d=5$,  - $\Omega(n^{d/3 + 2\sqrt{d}/9-o(\sqrt{d})})$ for general $d$,  assuming the 3-uniform hyperclique hypothesis. For Klee's measure problem andthe depth problem, these bounds improve previous lower bounds of$\Omega(n^{1.777...}), \Omega(n^{2.0833...})$ and $\Omega(n^{d/3 + 1/3 +\Theta(1/d)})$ respectively.  Our improved prefix covering designs were obtained by (1) exploiting acomputer-aided search using problem-specific insights as well as SAT solvers,and (2) showing how to transform combinatorial covering designs known in theliterature to strong prefix covering designs. In contrast, we show that ourlower bounds are close to best possible using this proof technique.

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions $d\ge 4$