On galleries with no bad points
type: Item
instance of: scholarly article
title: On galleries with no bad points
zbMATH Open document ID: 0927.52010
DOI: 10.1007/PL00009414
author: Pavel Valtr
published in: Discrete \& Computational Geometry
publication date: 1999-05-31T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 52A30
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 93C85
zbMATH DE Number: 1271044
zbMATH Keywords: art gallery
zbMATH Keywords: star-shaped set
zbMATH Keywords: guarding galleries
zbMATH Keywords: good points
zbMATH Keywords: Lebesgue and Borel measures
reviewed by: Serguey M. Pokas
MaRDI profile type: Publication
full work available at URL: pl00009414
OpenAlex ID: W2023996743
description: scientific article; zbMATH DE number 1271044