DIMACS TR: 96-55

On galleries with no bad points

Author: Pavel Valtr


For any $k$ we construct a simply connected compact set (art gallery) in $R^3$ whose every point sees a positive fraction (in fact, more than $5/9$) of the gallery, but the whole gallery cannot be guarded by $k$ guards. This disproves a conjecture of Kavraki, Latombe, Motwani, and Raghavan.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-55.ps.gz
DIMACS Home Page