Covering boxes by points (Q687139)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Covering boxes by points
scientific article

    Statements

    Covering boxes by points (English)
    0 references
    1 November 1993
    0 references
    In Euclidean \(d\)-space let \({\mathcal F}\) denote a family of closed orthotopes (the generalizations of the rectangle and the ``box'') with edges parallel to the coordinate axes. Let \(\nu({\mathcal F})\) denote the maximal number of pairwise disjoint members of \({\mathcal F}\) and \(\tau({\mathcal F})\) denote the minimal number of points in a set meeting all members of \({\mathcal F}\). The paper contributes new information about the numbers \(f(n,d)= \max_{\nu({\mathcal F}) \leq n} \tau({\mathcal F})\), for example: \(f(2,d) \leq d+1\) with equality for \(d=2, 3,4;\) \(f(2,d) \geq c'\sqrt d/ \log d\); \(f(3,2)=5\); \(f(4,2) \leq 8\); \(f(n,2) \leq n \log_ 2n+2-{n \over 2}\).
    0 references
    boxes
    0 references
    transversal
    0 references
    closed orthotopes
    0 references

    Identifiers