On the Union Complexity of Families of Axis-Parallel Rectangles with a Low Packing Number

Chaya Keller, Shakhar Smorodinsky

Abstract


Let $\mathcal{R}$ be a family of $n$ axis-parallel rectangles with packing number $p-1$, meaning that among any $p$ of the rectangles, there are two with a non-empty intersection. We show that the union complexity of $\mathcal{R}$ is at most $O(n+p^2)$, and that the $(k-1)$-level complexity of $\mathcal{R}$ is at most $O(n+k p^2)$. Both upper bounds are tight.


Keywords


Union complexity; Packing number; Combinatorial complexity; Axis-parallel rectangles

Full Text:

PDF