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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 03:40, 1 February 2024

scientific article
Language Label Description Also known as
English
On the union complexity of families of axis-parallel rectangles with a low packing number
scientific article

    Statements

    On the union complexity of families of axis-parallel rectangles with a low packing number (English)
    0 references
    0 references
    0 references
    22 November 2018
    0 references
    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.
    0 references
    union complexity
    0 references
    packing number
    0 references
    combinatorial complexity
    0 references
    axis-parallel rectangles
    0 references

    Identifiers