5. Applications of Helly’s Theorem in Combinatorial Geometry 21

8∗

(Colored Helly’s Theorem). Let A1,... , Ad+1 be non-empty finite families

of convex sets in

Rd.

Suppose that for each choice Ai ∈ Ai, i = 1, . . . , d + 1, we

have A1 ∩ . . . ∩ Ad+1 = ∅. Prove that for some i the intersection of the sets in the

family Ai is non-empty.

Hint: This can be deduced from Problem 2 of Section 2.3; see also [Bar82] and

Chapter 8 of [Mat02].

5. Applications of Helly’s Theorem in Combinatorial

Geometry

In the next two sections, we discuss various applications and appearances of Helly’s

Theorem. The proofs are almost immediate once we recognize the relationship

of the problem to Helly’s Theorem but may be quite non-trivial if we miss that

connection.

(5.1) Separating points by a hyperplane. Suppose that there is a finite set R

of red points in Rd and a finite set B of blue points in Rd. A hyperplane H ⊂ Rd is

the set described by a linear equation H = x ∈ Rd : c, x = α , where c = 0 is

a non-zero vector and α is a number. We say that the hyperplane H ⊂ Rd strictly

separates red and blue points if c, x α for all x ∈ R and c, x α for all x ∈ B.

The following result, called Kirchberger’s Theorem, was proved by P. Kirchberger

in 1903, that is, before Helly’s Theorem.

Proposition. Suppose that for any set S ⊂

Rd

of d+2 or fewer points there exists

a hyperplane which strictly separates the sets S ∩ R and S ∩ B of red, resp. blue,

points in S. Then there exists a hyperplane which strictly separates the sets R and

B.

Proof. A hyperplane H = x ∈ Rd : c, x = α , where c = (γ1, . . . , γd) ∈ Rd,

can be encoded by a point (c, α) = (γ1, . . . , γd,α) ∈ Rd+1. For every point r ∈ R

we define a set Ar ⊂

Rd+1:

Ar = (c, α) ∈

Rd+1

: c, r α

and for every point b ∈ B we define a set Ab ⊂ Rd+1:

Ab = (c, α) ∈

Rd+1

: c, b α .

It is clear that Ab and Ar are convex sets in Rd+1. Therefore, by Helly’s Theorem

the intersection

r∈R

Ar ∩

b∈B

Ab

is non-empty, provided for any subset S ⊂ R ∪ B of at most d + 2 points the

intersection

r∈S∩R

Ar ∩

b∈S∩B

Ab