pith. sign in

arxiv: 1702.00849 · v1 · pith:3EV4VESZnew · submitted 2017-02-02 · 🧮 math.CO · cs.CG

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

classification 🧮 math.CO cs.CG
keywords complexityrectanglesaxis-parallelnumberpackingunionboundsfamilies
0
0 comments X
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.