On three measures of non-convexity

Abstract: The invisibility graph

I (X)

of a set

X s u b s e t e q m a t h b b 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

o m e g a (I (X))

, the chromatic number

c h i (I (X))

and the convexity number

g a m m a (X)

, which is the minimum number of convex subsets of

X

that cover

X

. We settle a conjecture of Matouv{s}ek and Valtr claiming that for every planar set

X

,

g a m m a (X)

can be bounded in terms of

c h i (I (X))

. As a part of the proof we show that a disc with

n

one-point holes near its boundary has

c h i (I (X)) g e l o g l o g (n)

but

o m e g a (I (X)) = 3

. We also find sets

X

in

m a t h b b R^{5}

with

c h i (X) = 2

, but

g a m m a (X)

arbitrarily large.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: On three measures of non-convexity