Covering with Euclidean boxes (Q1091402)

The authors prove the following box cover theorem: For each dimension d there exists a constant c depending only on d such that any finite (or compact) set \(V\subset {\mathbb{R}}^ d\) contains a subset S with \(| S| \leq c\) and satisfying \(V\subset \cup_{p,q\in S}box(p,q)\) (box(p,q) denotes the smallest box containing p and q and whose faces are parallel to the coordinate axes of \({\mathbb{R}}^ d)\). For \(d=2\), the result was shown, with \(c=4\), by \textit{A. Gyárfás} and the second author [Combinatorica 3, 351-358 (1983; Zbl 0534.05052)]. As a first consequence of the box cover theorem, it is shown that if H is a d-dimensional box-hypergraph then \(\rho\) (H)\(\leq c_ 0\cdot \alpha (H)^ c\), where \(\alpha\) (H) and \(\rho\) (H) denote, respectively, the stability and the covering number of H, and c and \(c_ 0\) are constants depending only on d. Another consequence is the extension to the general case of boxes defined by arbitrary finite-cone-subdivisions of \({\mathbb{R}}^ d\). Geometric variants of these results, with boxes replaced by angles, are also derived.