Rutgers Discrete Math Seminar


An Art Gallery Theorem


Gil Kalai
Hebrew University, IAS and DIMACS


DIMACS Seminar Room 431
CoRE Building
Rutgers University


4:30 PM
Tuesday, November 14, 1995


We prove a conjecture of Kavraki, Latombe, Motwani and Raghavan that if $X$ is a compact simply connected set in the plane of Lebesgue measure 1, such that any point $x$ in $X$ sees a part of $X$ of measure at least epssilon, then one can choose a set $G$ of at most $f(\epsilon)$ points in $X$ such that any point of $X$ is seen by some point of $G$. More generally, if for any $k$ points in $X$ there is a point seeing at least 3 of them, then all points of $X$ can be seen >from at most $O(k^3\log k)$ points.

In the lecture we will try to put this result in the context of various recent result in geometry where the existence of large independent sets (in certain graphs or hypergraphs which come >from the geometric problem,) implies low chromatic number.

Joint work with Jiri Matousek.

Document last modified on November 8, 1995