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