Page 1 of 2

### bisection or something else..

Posted: Mon Apr 24, 2006 7:01 am
given the cartesian coordinates of three points A, B and C...

find a point D such that dis(A,D) + dis(B,D) + dis(C,D) is minimum..

where dis(a, b) is the euclidian distance between point a and b.

what is the approach to solve this kind of problem?

Posted: Mon Apr 24, 2006 7:34 am
how about if try all possibility.

D = A -> dis(B,D) + dis(C,D)

D = B -> dis(A,D) + dis(C,D)

D = C -> dis(A,B) + dis(B,D)

I think it should be give the minimum total distance

Posted: Mon Apr 24, 2006 7:38 am
but how can i be sure that D has to be one of the points A, B or C.
other points might give better result !!

Posted: Mon Apr 24, 2006 8:26 am
yeah you are right .

let Pab = middlePoint(A,B)
let Pac = middlePoint(A,C)
let Pbc = middlePoint(B,C)

Pab, Pac, Pbc can be candidate of D.

after that :

E = Pab, F=Pac, G=Pbc

let Pef = middlePoint(E,F)
let Peg = middlePoint(E,G)
let Pfg = middlePoint(F,G)

Pef, Peg, Pfg can be candidate of D.

repeat this procedure until the new three point are not same each other.
I think this method can give the better result from my last post.
I only try to help

Posted: Mon Apr 24, 2006 9:13 am
This is called the Steiner point (of a triangle), try feeding that into Google.

If I recall correctly, if the triangle has an angle larger than or equal to 120 degrees, then the answer is the vertex with the large angle. Otherwise it is a point in the interior of the triangle such that all three angles ADB, BDC and CDA are equal to 120 degrees.

(Edit:) If this is correct, one can find the answer in the second case by computing the intersection of two circle arcs (the set of points E such that angle AEB has 120 degrees is a union of two such arcs).

BTW, I think I saw this task in the past "Timus Top Coders" contest (although I didn't solve the contest). Is this where you have it from?

Posted: Tue Apr 25, 2006 7:15 am

http://mathworld.wolfram.com/FermatPoints.html

The problem is also called Fermat Point.
misof wrote: BTW, I think I saw this task in the past "Timus Top Coders" contest (although I didn't solve the contest). Is this where you have it from?
Yes.

### hmm

Posted: Tue Apr 25, 2006 9:23 am
The superset of this problem exists in UVa:

http://online-judge.uva.es/p/v102/10216.html

### hmm

Posted: Tue Apr 25, 2006 9:25 am
Another harder version exists in Dhaka regional 2002, although both may have small floating point problem.

### hmm

Posted: Tue Apr 25, 2006 9:53 am
Also a somewhat similar problem is

http://online-judge.uva.es/p/v106/10695.html

Posted: Tue Apr 25, 2006 2:37 pm
Another related problem is http://acm.uva.es/p/v102/10228.html
But there you have N<=100 points, instead of just 3.

Posted: Wed Apr 26, 2006 7:24 am
Is it possible to solve these problems without knowing the formulae. I mean, is it possible for someone to derive them during contest time.
Are these problems solvable using trivial trigonometry and proper applicaton of bisection method.

### hmm

Posted: Wed Apr 26, 2006 7:39 am
First of all these problems appeared in Online contests other than the Dhaka regional one. So it was ok.

It can be a debate on whether something is a trivial knowledge on a non-trivial one. Someone weak in graph problems can argue that matching problems are non-trivial, some one weak in number theory may argue that pick's theory is a non-trivial thing but both of them appear in contest So there is no point in making such arguments. Problems that require special knowledge appear in contests and will continue to appear.

Someone can say that those things taught in undergraduate level is trivial. But I can't remember any course that taught matching or pick's theorem. May be some better universities do teach them. So the inconsistency is there and so is the argument.

Posted: Wed Apr 26, 2006 6:00 pm
I learned about bipartite matching the second year in university, both through a discrete math class and an algorithms class.

Pick's Theorem I would consider more "special" knowledge. Though I guess if you study pure math and mainly combinatorics you might hear about it already as an undergrad.

(Even though I know both of them, I would not consider either of them to be "trivial" though.)

### Re: hmm

Posted: Thu Apr 27, 2006 11:50 am
shahriar_manzoor wrote:First of all these problems appeared in Online contests other than the Dhaka regional one. So it was ok.

It can be a debate on whether something is a trivial knowledge on a non-trivial one. Someone weak in graph problems can argue that matching problems are non-trivial, some one weak in number theory may argue that pick's theory is a non-trivial thing but both of them appear in contest So there is no point in making such arguments. Problems that require special knowledge appear in contests and will continue to appear.

Someone can say that those things taught in undergraduate level is trivial. But I can't remember any course that taught matching or pick's theorem. May be some better universities do teach them. So the inconsistency is there and so is the argument.
Actually, my post was more of a query than an argument. I am sorry, if I have given any false impression.

What I wanted to know, how most people solve these problems. Do they rely on their special knowledge or they use their intuition and skills to derive a solution. Of course, to do this, one would also require some knowledge, such as trigonometry and manipulation of equations. Now, considering the course contents of 12-Grade, A' Level, HSC etc, someone who really understands the topics of their books, these things are trivial.

Although I learned many properties of triangles at High School, I don't remember anything like these. That is why I made the query.

### hmm

Posted: Thu Apr 27, 2006 3:23 pm
The problems I mentioned are solvable by some sort of bisection but still one has to have the 120 degree knowledge. So without some special knowledge these can be difficult to solve or may be there is I am not sure.

AFAIK Steiner tree problems are open problems but when there is only one hub it is not open.

In any case I slightly misunderstood your post as well. And also the cause of misunderstanding is on a previous occasion I was asked by you or your brother are questions requiring special knowledge fit for contests...