GUARDING GALLERIES WHERE NO POINT SEES A SMALL-AREA

We prove the following result which is the planar version of a conject ure of Kavraki, Latombe, Motwani, and Raghavan: there is a function f( h, epsilon) polynomial in h and 1/epsilon such that if X is a compact planar set of Lebesgue measure 1 with h holes, such that any point x i s an element of X sees a part of X of measure at least epsilon, then t here is a set G of at most f(h, epsilon) points (guards) in X such tha t any point of X is seen by at least one point df G. With a high proba bility, a set G of f(h, epsilon) random points in X (chosen uniformly and independently) has the above property. In the proof (giving f(h, e psilon) less than or equal to (2 + o(1))1/epsilon log 1/epsilon log(2) h) we apply ideas of Kalai and Matousek who proved a weaker bound f(h , epsilon) less than or equal to C(h) 1/epsilon log 1/epsilon, where C (h) is a 'quite fast growing function' of h. We improve their bound by showing a stronger result on the so-called VC-dimension of related se t systems.