On the union complexity of families of axis-parallel rectangles with a low packing number
classification
🧮 math.CO
cs.CG
keywords
complexityrectanglesaxis-parallelnumberpackingunionboundsfamilies
read the original abstract
Let 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 R is at most O(n+p^2), and that the (<=k)-level complexity of R is at most O(kn+k^2p^2). Both upper bounds are tight.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.