TY - JOUR
T1 - On the union complexity of families of axis-parallel rectangles with a low packing number
AU - Keller, Chaya
AU - Smorodinsky, Shakhar
N1 - Publisher Copyright:
© The authors.
PY - 2018
Y1 - 2018
N2 - 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 + p2), and that the (k − 1)-level complexity of R is at most O(n + kp2). Both upper bounds are tight.
AB - 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 + p2), and that the (k − 1)-level complexity of R is at most O(n + kp2). Both upper bounds are tight.
UR - http://www.scopus.com/inward/record.url?scp=85061594845&partnerID=8YFLogxK
U2 - 10.37236/6792
DO - 10.37236/6792
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:85061594845
SN - 1077-8926
VL - 25
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 4
M1 - #P4.32
ER -