GeeCON Prague 2014*
The moose likes Programming Diversions and the fly likes Another interesting geometry problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Another interesting geometry problem" Watch "Another interesting geometry problem" New topic
Author

Another interesting geometry problem

Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 588
    
  11
(from a Maths Olympiad more than a decade ago)

You have four points A, B, C and D, in the same plane, no three points lying on a straight line.
(i.e. no three being collinear).
First question: find a point E in the plane such that AE + BE + CE + DE is minimal
Second question: prove that your answer to the first question is correct
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
First guess for the first question after thinking about it for only twenty seconds:

Two cases: Either A, B, C, D make a convex or a concave quadrilateral.
- If convex, E is at the intersection of the two diagonals.
- If concave, E is at the one point that is at the concave angle.

Still thinking about it.

Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4397
    
    8

That's what I thought as well. Here's an argument (though probably not a proof) that it's at least a local minimum.

Case 1: Convex, with E the intesect of AC and BD.

Points on the line AC have a minimal value of AE + CE (and AE + CE is constant along that line). Points on the line BD have a minimal value of BE + DE. So we can minimise those two contributions independently, and that occurs at the intersection.

Case 2: Concave, with D within the triangle ABC.

Starting at D, any small move towards A keeps AE + DE unchanged. But both BE and CE increase, so the total sum of differences must increase. A similar argument applies to moving towards B or C. So any infinitesimal move in any other direction is also going to increase the sum (to the first order we can consider it a superposition in steps towards two of the other points.

So, which parts of that argument do you think need shoring up the most?
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
That was the exact same "proof" I had in mind, but you put it more concisely than I was about to.

The only part that wasn't immediately obviously correct to me is if you let point E in case 2 move directly away from one of the points that make up the outer triangle. i.e. Point A, B or C to use your labeling. However, any movement of E directly away from A by some small amount x, adds 2x to the total distance because of AE and DE but only decreases the total distance for CE and BE by x multiplied by some sine or cosine for each. Ok, it took a couple seconds, but I'm convinced.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
What if we remove the noncolinearity restriction? How many additional cases does that add, and what are the answers for those cases?
Ivan Jozsef Balazs
Rancher

Joined: May 22, 2012
Posts: 867
    
    5
from a Maths Olympiad more than a decade ago


Did you take part?
Ivan Jozsef Balazs
Rancher

Joined: May 22, 2012
Posts: 867
    
    5
Case 1: Convex, with E the intesect of AC and BD.


Let us fabricate a horizontal table from a frictionless material and drill small holes at the points A,B,C,D into it.
Let us take equal weights and attach strings to them, and put the strings through the holes, and bind together to a point on the upper size of the table, with the weighs hanging down.
We then let the things loose and wait until they finds the equilibrium. The strings will stretch to make straight stages.

On the one hand the weights tend to hang towards the Earth as far as they can, so the sum of the strings hanging down below the table gets maximized, that is, the sum of the lengths on the table gets minimized.

On the other hand the middle point where the strings are stitched together does not move any longer if the forces working on it cancel out.

So for which point E is it true, that the unity vectors (the weigths are equal, so the gravity forces are equal) pointing from E towards A,B,C,D cancel each other out when summed up?
Well, two unity vectors pointing out from a given point yield a sum whose size is proportional to the cosine of the half angle between the directions, and the direction is that of the bisetrix.

From here it follows (I am not not able to provide a figure...) that the angle EA,EB must be equal to the angle EC,ED and the bisectrices must point to opposite directions, which is possible if E is the intesect of AC and BD.

(Huh, that was hard! Not only is English not my first language, arguably not even the second best, and even though I learned and studied maths, never in English.)

Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 588
    
  11
hi Ivan,

no, I did not attend this Olympiad! At my age, I'm glad enough to even remember the whole thing!

Still reading your last post, looks interesting, but I have not gotten it yet (again the old age?).

And for all the other contributions: to my shame I must admit that I only thought of normal, ordinary
day-to-day convex quadrilaterals. Therefore, I've kept very quiet all the time...

Greetz,
Piet
Ivan Jozsef Balazs
Rancher

Joined: May 22, 2012
Posts: 867
    
    5
Which part was not clear?

The physics part is a substitute for working with derivatives.

Let me rephrase the geometry part with complex numbers.
So we have four unity complex numbers (that is, ones with 1 as the absolute value) which sum up to zero and we want to prove that they cancel out pairwise.
(If one pair cancels out, then the other must also.)
So zi (i=1,2,3,4) are unity complex numbers and they sum up to zero:
z1+z2+z3+z4 = 0

z1+z2 = - z3 - z4

If both sides equal, so we can take the square of the absolute value, that is, if we multiply both sides with their complex conjugates:

(*) (z1+z2)(co(z1)+co(z2)) = the same with z3 and z4

Let ci denote co(zi), the conjugate value of zi.

zi is unity absolute value, so zi.ci = 1


So the left side of (*) looks like this:
(z1+z2).(c1+c2) = z1.c1 + z2.c1+z1.c2+z2.c2 = 2 + z2/z1 + z1/z2

The right side is 2 + z3/z4 + z4/z3

So z1/z2 + z2/z1 = z3/z4 + z4/z3

z2/z1 is a unity complex number, so it can be written like this: exp(i.a) = cos(a)+ i.sin(a)
then z1/z2 = cos(a)-i.sin(a) and z1/z2 + z2 / z1 = 2 .cos(a)

Likewise z3/z4 = exp(i.b) = cos(b) + i sin (b)
z4/z3 = cos(b) - i sin (b) and z3/z4 + z4/z3 = 2.cos(b)

So cos(a) and cos(b) equal! Then either sin(a)=sin(b) or sin(a)=-sin(b).

If on the one hand the sin values are equal, then z1/z2 = z3/z4, and let us denote this common value with w, so we have

0 = z1+z2+z3+z4 = w.z2+z2 + w.z4+ z4 = (1+w).(z2+z4)

Now if 1+w = 0, then w = -1, so z1 and z2 and z3 and z4 cancel out pairwise,
if 1+w != 0, then z2+z4 = 0.


If on the other hand sin(a)=-sin(b), then if w = cos(a)+i.sin(a) then z1/z2 = w, z4/z3 = w,
and the above computation can be applied for z1,z2,z4,z3:
either z1 and z2 and z3 and z4 cancel out pairwise, or z2+z3 = 0.

(RANT:
The forum software won't let me use the letter
The specific error message is: "u" is a silly English abbreviation; use "you" instead.

In theory I agree and also detest SMS-speak styled abbreviations in the forums, the letter is appropriate as a variable name. SIGH.
)
Ivan Jozsef Balazs
Rancher

Joined: May 22, 2012
Posts: 867
    
    5
A friend suggests this solution for the following excercise:
There are 4 unity vectors in the plane which sum up to zero. It follows that they cancel out pairwise.

Here is why. We have four unity vectors z1,z2,z3,z4 that sum up to zero.
Let us consider the points 0, z1=X, z1+z2=Y, z1+z2+z3=Z, z1+z2+z3+z4=0.
So X and Z are both of unity distance from 0 and Y, so they either equal or they lie symmetric.

In either case, the vectors cancel out pairwise.
 
GeeCON Prague 2014
 
subject: Another interesting geometry problem