From: jaf@siesta.cs.wustl.edu (Andy Fingerhut)
Newsgroups: sci.math
Subject: A conjecture about 6 points in the Euclidean plane
Date: 14 Jul 1995 17:26:38 -0500
Organization: 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.edu
Subject: A conjecture about 6 points in the Euclidean plane
Date: Mon, 18 Sep 1995 15:14:17 -0700
From: 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/