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
Previous Page Next Page