Three measures of non-convexity of a set in Rd will be discussed. The invisibility graph I(X) of a set X⊆Rd is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in X. We consider the following three parameters of a set X: the clique number ω(I(X)), the chromatic number χ(I(X)) and the minimum number γ(X) of convex subsets of X that cover X. Observe that ω(X)≤χ(X)≤γ(X) for any set X, where ω(X):=ω(I(X)) and χ(X)=χ(I(X)).
Here is a sample of results comparing the above three parameters:
Let X⊆R2
be a planar set with ω(X)=ω<∞ and with no one-point holes. Then γ(X)≤O(ω4)
.
For every planar set X
, γ(X) can be bounded in terms of χ(X)
.
There are sets X
in R5 with χ(X)=3, but γ(X)
arbitrarily large.
The talk is based on joint papers with J. Matoušek, J. Cibulka, M. Korbelář, M. Kynčl, V. Mészáros, and R. Stolař.

## Watch SlidesLive on mobile devices

© SlidesLive Inc.