Geodesic
On the union complexity of families of axis-parallel rectangles with a low packing number
Chaya Keller1 ; Shakhar Smorodinsky1
1Ben-Gurion University of the NEGEV
The electronic journal of combinatorics, Tome 25 (2018) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/6792
Classification : 52C45, 52C15
Mots-clés : union complexity, packing number, combinatorial complexity, axis-parallel rectangles

Chaya Keller  1   ; Shakhar Smorodinsky  1

1 Ben-Gurion University of the NEGEV 
@article{10_37236_6792,
     author = {Chaya Keller and Shakhar Smorodinsky},
     title = {On the union complexity of families of axis-parallel rectangles with a low packing number},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {4},
     doi = {10.37236/6792},
     zbl = {1403.52014},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6792/}
}
TY  - JOUR
AU  - Chaya Keller
AU  - Shakhar Smorodinsky
TI  - On the union complexity of families of axis-parallel rectangles with a low packing number
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6792/
DO  - 10.37236/6792
ID  - 10_37236_6792
ER  - 
%0 Journal Article
%A Chaya Keller
%A Shakhar Smorodinsky
%T On the union complexity of families of axis-parallel rectangles with a low packing number
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6792/
%R 10.37236/6792
%F 10_37236_6792
Chaya Keller; Shakhar Smorodinsky. On the union complexity of families of axis-parallel rectangles with a low packing number. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/6792

Cité par Sources :