ON THREE MEASURES OF NON-CONVEXITY

Investor logo
Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

CIBULKA Josef KORBELÁŘ Miroslav KYNCL Jan MESZAROS Viola STOLAR Rudolf CIBULKA J. VALTR Pavel

Year of publication 2017
Type Article in Periodical
Magazine / Source Israel journal of mathematics
MU Faculty or unit

Faculty of Science

Citation
Web Full Text
Doi http://dx.doi.org/10.1007/s11856-017-1467-1
Keywords CONVEX-SETS; DECOMPOSITION THEOREMS; SUBSETS; UNION; PLANE
Description The invisibility graph I (X) of a set X subset of R-d 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 omega(I(X)), the chromatic number chi(I(X)) and the convexity number gamma(X), which is the minimum number of convex subsets of X that cover X. We settle a conjecture of Matousek and Valtr claiming that for every planar set X, gamma(X) can be bounded in terms of chi(I( X)). As a part of the proof we show that a disc with n one-point holes near its boundary has chi(I(X)) >= log log(n) but omega (I(X)) = 3. We also find sets X in R-5 with chi(X) = 2, but gamma( X) arbitrarily large.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.