From: jaf@siesta.cs.wustl.edu (Andy Fingerhut)Newsgroups: sci.mathSubject: A conjecture about 6 points in the Euclidean planeDate: 14 Jul 1995 17:26:38 -0500Organization: Washington University, St. Louis MO
This isn't a homework problem -- it is one from my research.It may be as easy as a homework given in some class somewhere,and if so, I'd be delighted to know the answer. If you know ofa proof, you'll either get a sincere acknowledgement in a resultingpaper, or perhaps even be asked if you want to be a co-author ofthe resulting paper.(Before you get too excited about this possibility, or spend too muchtime on this conjecture, my colleagues and I are also trying to find aproof for a conjecture that would supersede this result, and if we findit, this proof may never see the pages of a journal.)Conjecture----------You are given 6 arbitrary points in the euclidean plane. Technical detail: The conjecture allows more than one of the points to be at the same location. Assume that the points are identified by some names other than their coordinates, so that two points that happen to be at the same place are still considered different points.Find a maximum matching for these 6 points, Defn: A matching on a set of n points is a set of n/2 pairs of points, such that no two pairs contain a common point. The length of a single pair is equal to the Euclidean distance between the points of the pair. The length of a matching is the sum of all n/2 pair lengths. I only care about matchings with the maximum length among all possible matchings.Let the matching be {{a_1, b_1}, {a_2, b_2}, {a_3, b_3}}.Prove that there must exist a point x such that for all i, 1 < i < 3,dist(a_i, x) + dist(x, b_i) < 2/sqrt(3) * dist(a_i, b_i)where dist(x, y) is the Euclidean distance between x and y.Why do I care?--------------One interesting consequence is that if such a point exists for any 6 pointsin the plane, then it also must exist for _any_ even number points in theplane.To see this, note that one way to interpret the statement:dist(a_i, x) + dist(x, b_i) < 2/sqrt(3) * dist(a_i, b_i)is to note that the set of all such points x lie inside an ellipsewith foci a_i and b_i. If we denote this set of points byell(a_i, b_i, 2/sqrt(3)), then the conjecture says that the threeell sets must have a common point.If this were true, then we could prove the conjecture for any evennumber of points by applying Helly's Theorem, described below.Helly's Theorem---------------(Sorry, I don't have a reference, and I don't even know if I spelledHelly correctly. I've heard that Helly was Hungarian, and he provedthis theorem while he was jailed during World War II. If you areinterested in a citation, let me know and I'll ask the person I heardit from.)Given any collection of convex sets in R^2, if all sub-collectionsof exactly 3 of these sets have a common point, then all n sets havea common point.I've also heard that this generalizes if you replace R^2 with R^k, and3 with (k+1). Pretty neat, I thought.Where did 2/sqrt(3) come from?------------------------------I know that the conjecture is false if 2/sqrt(3) is replaced withanything smaller. To see this, choose the six points such that twoof them are at each of the vertices of an equilateral triangle. Thenthe only point x that satisfies the conjecture is the center of thetriangle.The conjecture may be false for 2/sqrt(3). If you know of acounterexample, please let me know. In general, I'd like to prove theconjecture for as small a constant (in place of 2/sqrt(3)) as possible.Why do I care about proving this?---------------------------------The following is just a quick summary. If you want more details,just ask and I'll spend more time writing up details.It relates to an abstract version of a problem in designing communicationnetworks. The given points represent nodes that should be connectedby a network. The length of a maximum matching is a lower bound onthe cost of any feasible network, and the point x is a place where I'dlike to place the center of a "star" network, in which all given pointsare connected directly to the star.If the conjecture is true, I can show that a star network costs at most2/sqrt(3) times more than an optimal solution.Have I made any progress myself, before asking the net?-------------------------------------------------------Only a little.Think of the matching of the 6 points as a set of 3 line segments.Each line segment joins one of the pairs of points.If every pair of line segments intersects at a single point,then consider the triangle with these three intersecting points as itsvertices. For any triangle, there exists a point x in its interioror its boundary such that each side of the triangle subtends an angleof at least 120 degrees from x. If a line segment AB subtends an angleof at least 120 degrees from x, thendist(A,x) + dist(x,B) < dist(A,B)Therefore x satisfies the conjecture.Someone else working on this conjecture tried breaking it up into casesbased on the number of intersections between the 3 line segments.The above shows that if there are 3 intersections, the conjecture holds.The cases for 0, 1, or 2 intersections are still eluding me.Thank you for taking the time to read this.Andy FingerhutApplied Research Laboratory <-- this line is optional ifWashington University, Campus Box 1045/Bryan 509 you have limited spaceOne Brookings DriveSaint Louis, MO 63130-4899 Tel: 314-935-6110Fax: 314-935-7302Internet: jaf@arl.wustl.edu
To: jaf@siesta.cs.wustl.eduSubject: A conjecture about 6 points in the Euclidean planeDate: Mon, 18 Sep 1995 15:14:17 -0700From: David Eppstein <eppstein@ICS.UCI.EDU>
Hi --You sent out this message a couple months ago,did you get any response? You are given 6 arbitrary points in the euclidean plane. Find a maximum matching for these 6 points, Let the matching be {{a_1, b_1}, {a_2, b_2}, {a_3, b_3}}. Prove that there must exist a point x such that for all i, 1 < i < 3, dist(a_i, x) + dist(x, b_i) < 2/sqrt(3) * dist(a_i, b_i)I think I can prove it with a worse constant,and directly for any number of points (rather than applying Helly).Also it seems to work for bichromatic point sets as well:let (a1,b1) be shortest edge in the matching, and let xbe any point on that edge.Then if d(ai,x)+d(bi,x) > 3 d(ai,bi)you could replace (a1,b1)&(ai,bi) by (a1,bi)&(ai,b1)which have total weight (by triangle inequality) > 3d(ai,bi)-d(a1,b1) > d(a1,b1)+d(ai,bi).Therefore your result seems to hold with 3 instead of 2/sqrt 3. With alittle more care this can be improved (for the monochromatic case only):if you take x to be the midpoint of (a1,b1), then one of a1,b1 is alwaysfarther from ai or bi than x, so you only need to apply the triangleinequality on one of the two replacement edges and you get a factor of 2.5.-- David Eppstein UC Irvine Dept. of Information & Computer Scienceeppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/