Rutgers Discrete Math Seminar
Title:
An Art Gallery Theorem
Speaker:
- Gil Kalai
- Hebrew University, IAS and DIMACS
Place:
- DIMACS Seminar Room 431
- CoRE Building
- Rutgers University
Time:
- 4:30 PM
- Tuesday, November 14, 1995
Abstract:
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