wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Intersecting Convex Hulls (9/3/2002)
        
(Message started by: william wu on Sep 3^rd, 2002, 6:49pm)

Title: Intersecting Convex Hulls (9/3/2002)
Post by william wu on Sep 3^rd, 2002, 6:49pm

The Convex Hull of a set P of points is the smallest convex set containing P. Show that any set of at least N+2 distinct points in an N-dimensional real vector space can be partitioned into two disjoint subsets whose two convex hulls have a nonempty intersection. For example, in the plane (N=2) any four distinct points are either three vertices of a triangle plus a point inside it, or else four vertices of a quadrilateral whose diagonals intersect. (Problem suggested by George Bergman. A Convex Set in a linear space is one that includes, with any two points in the set, also the line segment joining them. Consequently included too is every positively weighted average of any subset of points in the convex set; can you see why?)

Title: Re: Intersecting Convex Hulls
Post by Pietro K.C. on Sep 5^th, 2002, 4:54pm

VERY beautiful problem. :)

I think I have a solution, which I'll write in high-level math (in the programming language sense). How did you do it?

Mine is by induction. For N = 1, 3 points on the real line, just pick the least and greatest and the middle one will be in that interval.

Now suppose N-dimensional space and a set S of N+2 points in it. If N+1 of them are in the same hyperplane, then the problem reduces to the (N-1)-dimensional case with N+1 points, which we suppose solved by the induction hypothesis. If there are no N+1 points on the same hyperplane (in which case any set of N vectors is linearly independent, a result easily established), take N points at random from S, call this subset A, and call the remaining two points u and v. Let r = CH({u,v}) (the convex hull of the set {u,v}, which is the straight line between u and v).

Since the N points of A are linearly independent, they determine a unique hyperplane H; if r intersects H, say at w, let A' = A U {w}. Then A' has N+1 elements and is embedded in (N-1)-dimensional space, so it has disjoint subsets B and C such that CH(B) intersects CH(C). Let w belong to B, and let B' = (B-{w}) U {u, v}. Then CH(B) is contained in CH(B') and B', C are disjoint subsets of A such that their convex hulls intersect, which is what we wished to construct.

This treats the case where r intersects H. Now we will show that, given N+2 points in N-space, no N+1 of which are on the same hyperplane, it is always possible to pick N such that the hyperplane determined by them intersects the straight line connecting the remaining two. Furthermore, we will show that the choice of N-1 of these N points can be made arbitrarily.

Suppose now that A is any subset of S containing N-1 points. The remaining three are not colinear, since otherwise we would have some set of N+1 points on the same hyperplane. Let these points be u, v and w, and T the 2-plane they determine.

For the same reason, the hyperplane H(A,u) determined by A and u cannot contain v or w, and similarly for H(A,v), H(A,w). Because of this, the intersection of H(A,u) with T is a straight line, since if it were 2-dimensional all of T would be included, and therefore v and w. The same result is valid for H(A,v) and H(A,w).

Now, for the interesting part. Let <A> be the subspace generated by A, and (A inter B) the intersection of the sets A and B.

First of all, the intersections of H(A,u), H(A,v), H(A,w) with T are disjoint; because (H(A,u) inter T) inter (H(A,v) inter T) = (H(A,u) inter H(A,v)) inter T = <A> inter T = empty; if <A> inter T were not empty, it could not include u, v or w, and would be a straight line not through those points; but in that case H(A,u) inter T would include two linearly independent vectors in T, and so all of T.

If the intersections above are disjoint, and are straight lines in T, they must be parallel; but if three lines p,q,t in a plane are parallel, one must lie between the other two, say q between p and t. It therefore cuts any segment from a point in p to one in t.

Let v be the point such that H(A,v) inter T = q; then CH({u,w}) intersects H(A,v), and H(A,v) is the hyperplane we wished to find. Now we apply this lemma to the preceding discussion and complete the demonstration of the theorem.