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

  • Chaya Keller
  • Shakhar Smorodinsky
Keywords: Union complexity, Packing number, Combinatorial complexity, Axis-parallel rectangles


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.

Article Number