anderson@uwvax.UUCP (David P. Anderson) (10/20/84)
<> This is one of my favorites. You have sets X and Y of points in the plane, each with n elements. Assume that no three points in X u Y are colinear. Prove or give a counterexample: there is a set of line segments, each of which has one endpoint in X and the other in Y, and of which any two segments are disjoint. Hint: the solution is simple and doesn't use any geometry outside of the triangle inequality. David Anderson (uwvax!anderson)
eklhad@ihnet.UUCP (K. A. Dahlke) (10/23/84)
< x --- y > This proof is not what you had in mind, since it does not use the triangular inequality, but you might find it interesting. Mine is an inductive proof, the first case being trivially true (one line segment connecting the point in x to the point in y). For the larger sets, we shall divide and conquer. Chose the point farthest to the right (the lower if two such points exist). Label the sets so this point (p) is in x, and draw a line through p (a virtually vertical line) such that x and y lie entirely on the half-plane bounded by this line. Rotate the line around p, and increment a counter when you cross a point in x, and decrement the counter when you cross a point in y. Begin the counter at 1 (since the line has already hit p (in the set x)). The counter must reach 0 after a rotation of 180 degrees (if not sooner). Since no three points are collinear, the counter presents a continuous function (in a discrete sort of way). It begins positive (at 1), wonders around up there, and becomes 0 upon crossing some point in y. It may become 0 several more times, but we don't care. Draw the line connecting p to the point in y which first makes the counter 0. There are an equal number of x and y points on either side of this line, and both half-planes can be "segmented" independently. I hope someone posts the "triangular" proof, i would be very interested. -- Karl Dahlke ihnp4!ihnet!eklhad
td@alice.UUCP (Tom Duff) (10/23/84)
The problem is: Given two sets each of n points in the plane, no 3 collinear, prove that each point in one set can be paired with a point in the other set such that none of the resulting line segments intersect. Consider the following algorithm: pick a pairing arbitrarily while there exist two intersecting lines AB and CD replace AB and CD by AD and CB Clearly, if this algorithm terminates it finds the required pairing. To prove termination we need only note that there is a finite number (factorial(n), actually) of possible pairings, and look at the sum of the lengths of the lines in each pairing. Each iteration of the loop decreases the sum (that's where you need the triangle inequality.) Since there are only a finite number of different lengths, the loop must eventually terminate.
td@alice.UUCP (Tom Duff) (10/23/84)
(regarding my posted proof.) Of course, a *real* mathematician wouldn't resort to writing a computer program and proving that it terminates -- you wouldn't want to haul in all that Turing baggage and recursive function theory for a simple geometry problem. Instead, he'd order all possible pairings by the sum of the lengths of the line segments, assume that a minimal pairing has an intersection and prove a contradiction. On the other hand, using my proof you can actually find the required pairing.
nemo@rochester.UUCP (Wolfe) (10/25/84)
> The problem is: > Given two sets each of n points in the plane, no 3 collinear, > prove that each point in one > set can be paired with a point in the other set such that none of the resulting > line segments intersect. Consider the following algorithm: > > pick a pairing arbitrarily > while there exist two intersecting lines AB and CD > replace AB and CD by AD and CB > > Clearly, if this algorithm terminates it finds the required pairing. To prove > termination we need only note that there is a finite number (factorial(n), actually) > of possible pairings, and look at the sum of the lengths of the lines in each > pairing. Each iteration of the loop decreases the sum (that's where you > need the triangle inequality.) Since there are only a finite number of different > lengths, the loop must eventually terminate. The algorithm does *NOT* necessarily terminate. There are configurations and pairings which cycle (left to the reader ...). A proof that there is a solution is as follows. First, define the *length of a pairing* on a set of points as the sum of the lengths of the segments connecting the pairs. Then define a *minimal pairing* as one whose length is less than or equall to any other pairing on the points (satisfying the problem's constraints). Now, note that 1) there are (as you note) only a finite number of pairings 2) therefore there exist minimal pairings in the set of possible pairings 3) No minimal pairing can have intersecting segments (by the triangle inequality, since as you note above, replacing intersecting segments (A1, B1) and (A2, B2) which intersected at point C by (A1, B2) and (A2, B1) in effect replaces segments (A1, C) and (C, B2) by (A1, B2), and segments (A2, C) and (C, B1) by (A2, B1), which reduces the sum of the lengths). 4) Hence, any minimal pairing will be a solution. How to get a minimal pairing is another problem. Nemo
nemo@rochester.UUCP (Wolfe) (10/25/84)
Sorry about the (false) claim that the algorithm you gave could loop. The reduction in length contradicts this, as you stated. Nemo (it won't be the last time I put my foot in it)