Author 
Topic: Intersecting Convex Hulls (9/3/2002) (Read 3229 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Intersecting Convex Hulls (9/3/2002)
« on: Sep 3^{rd}, 2002, 6:49pm » 
Quote Modify

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 Ndimensional 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?)

« Last Edit: Sep 16^{th}, 2002, 1:59pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: Intersecting Convex Hulls
« Reply #1 on: Sep 5^{th}, 2002, 4:54pm » 
Quote Modify

VERY beautiful problem. I think I have a solution, which I'll write in highlevel 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 Ndimensional 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 (N1)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 (N1)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 Nspace, 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 N1 of these N points can be made arbitrarily. Suppose now that A is any subset of S containing N1 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 2plane 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 2dimensional 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.


IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



