Guarding galleries where every point sees a large area

We prove a conjecture of Kavraki, Latombe, Motwani and Raghavan that ifX is a compact simply connected set in the plane of Lebesgue measure 1, such that any pointx∈X sees a part ofX of measure at least ɛ, then one can choose a setG of at mostconst1/ɛ log 1/ɛ points inX such that any point ofX is seen by some point ofG. More generally, if for anyk points inX there is a point seeing at least 3 of them, then all points ofX can be seen from at mostO(k ³ logk) points. Research supported by grants from the Sloan Foundation, the Israeli Academy of Sciences and Humanities, and by G.I.F. Research supported by Czech Republic Grant GAČR 201/94/2167 and Charles University grants No. 351 and 361. Part of the work was done while the author was visiting The Hebrew University of Jerusalem.