Informace o publikaci

ON THREE MEASURES OF NON-CONVEXITY

Autoři

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

Rok publikování 2017
Druh Článek v odborném periodiku
Časopis / Zdroj Israel journal of mathematics
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www Full Text
Doi http://dx.doi.org/10.1007/s11856-017-1467-1
Klíčová slova CONVEX-SETS; DECOMPOSITION THEOREMS; SUBSETS; UNION; PLANE
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info