Helly-type theorems for approximate covering (Q5896959)

We are given a family \(F\) of convex sets and another convex set \(U\). \(F\) covers \(U\) if the union of the elements of \(F\) contains \(U\). In this paper the authors look at the following problem: Given a covering \(F\) of a set \(U\), a small subset of \(F\) that covers most of \(U\) is looked for. If the elements of \(F\) as well as \(U\) are subsets of a geometric space an \(\varepsilon\)-covering of \(U\) is defined as a collection of sets whose union covers \(U\) except of a volume of at most \(\varepsilon\). In the case where all sets are in \(R^d\), let \(H_{\varepsilon}\) denote a smallest \(\varepsilon\)-covering of \(U\) contained in \(F\). If the elements in \(F\) have similar size, then the size of \(H_{\varepsilon}\) is bounded polynomially in \(1/{\varepsilon}\). Similar results hold for unit balls in \(R^d\) or smooth convex sets of bounded curvature. The results are extended to visibility occlusion among disjoint unit balls in \(R^3\). For covering by squares or balls and visibility in 3D, algorithms are presented giving either a point in \(U\) not covered by \(F\) or an \(\varepsilon\)-covering of \(U\) contained in \(F\).