On galleries with no bad points (Q1283765)

Consider an art gallery (i.e., compact set) \(X\) of Lebesgue measure 1 in \(\mathbb{R}^d,\) \(d\geq 2,\) such that a guard placed anywhere in the gallery sees a region of Lebesgue measure at least \(\varepsilon.\) Kavraki et al. conjectured that if \(X\) has at most \(h\) holes, then it can be guarded by at most \(f_d(h,\varepsilon)\) guards, for some function \(f_d\) polynomial in \(h\) and \(1/\varepsilon\) [\textit{L. Kavraki, J.-C. Latombe, R. Motwani} and \textit{P. Raghavan}, ACM Symp. Theoret. Comput., 353-362 (1995)]. In this paper the author disproves the conjecture of Kavraki et al. for \(d \geq 3.\) For any \(k\geq 1,\) it is constructed a simply connected gallery in \(\mathbb{R}^3,\) in which each point sees more than 5/9 of the gallery, but the whole gallery cannot be guarded by \(k\) guards. On the other hand, the following upper bound holds: for \(d \geq 2\) and \(\omega > 0,\) any \((d/(d+1)+\omega)\)-good compact gallery in \(\mathbb{R}^d\) can be guarded by one guard (in other words, it is star-shaped). Some related results for other Borel measures than the uniform (Lebesgue) one are proved.