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 of a proof, you'll either get a sincere acknowledgement in a resulting paper, or perhaps even be asked if you want to be a co-author of the resulting paper. (Before you get too excited about this possibility, or spend too much time on this conjecture, my colleagues and I are also trying to find a proof for a conjecture that would supersede this result, and if we find it, 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 points in the plane, then it also must exist for _any_ even number points in the plane. 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 ellipse with foci a_i and b_i. If we denote this set of points by ell(a_i, b_i, 2/sqrt(3)), then the conjecture says that the three ell sets must have a common point. If this were true, then we could prove the conjecture for any even number 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 spelled Helly correctly. I've heard that Helly was Hungarian, and he proved this theorem while he was jailed during World War II. If you are interested in a citation, let me know and I'll ask the person I heard it from.) Given any collection of convex sets in R^2, if all sub-collections of exactly 3 of these sets have a common point, then all n sets have a common point. I've also heard that this generalizes if you replace R^2 with R^k, and 3 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 with anything smaller. To see this, choose the six points such that two of them are at each of the vertices of an equilateral triangle. Then the only point x that satisfies the conjecture is the center of the triangle. The conjecture may be false for 2/sqrt(3). If you know of a counterexample, please let me know. In general, I'd like to prove the conjecture 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 communication networks. The given points represent nodes that should be connected by a network. The length of a maximum matching is a lower bound on the cost of any feasible network, and the point x is a place where I'd like to place the center of a "star" network, in which all given points are connected directly to the star. If the conjecture is true, I can show that a star network costs at most 2/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 its vertices. For any triangle, there exists a point x in its interior or its boundary such that each side of the triangle subtends an angle of at least 120 degrees from x. If a line segment AB subtends an angle of at least 120 degrees from x, then dist(A,x) + dist(x,B)<dist(A,B) Therefore x satisfies the conjecture. Someone else working on this conjecture tried breaking it up into cases based 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 Fingerhut Applied Research Laboratory <-- this line is optional if Washington University, Campus Box 1045/Bryan 509 you have limited space One Brookings Drive Saint Louis, MO 63130-4899 Tel: 314-935-6110 Fax: 314-935-7302 Internet: 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 x be 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 a little 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 always farther from ai or bi than x, so you only need to apply the triangle inequality on one of the two replacement edges and you get a factor of 2.5. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/