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