GUARDING GALLERIES WHERE EVERY POINT SEES A LARGE-AREA

We prove a conjecture of Kavraki, Latombe, Motwani and Raghavan that i f X is a compact simply connected set in the plane of Lebesgue measure 1, such that any point x is an element of X sees a part of X of measu re at least epsilon, then one can choose a set G of at most const 1/ep silon log 1/epsilon points in X such that any point of X is seen by so me point of G. More generally, if for any k points in X there is a poi nt seeing at least 3 of them, then all points of X can be seen from at most O(k(3) logk) points.