On the union complexity of families of axis-parallel rectangles with a low packing number (Q1627208)

Summary: 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.