Page 1 of 2

bisection or something else..

Posted: Mon Apr 24, 2006 7:01 am
by sohel
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
by Timo
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
:D

Posted: Mon Apr 24, 2006 7:38 am
by sohel
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
by Timo
yeah you are right :D .

how about this one

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 :D

Posted: Mon Apr 24, 2006 9:13 am
by misof
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
by sohel
thanks.. i googled for a bit and found the answer.

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
by shahriar_manzoor
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
by shahriar_manzoor
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
by shahriar_manzoor
Also a somewhat similar problem is :)

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

Posted: Tue Apr 25, 2006 2:37 pm
by mf
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
by shamim
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
by shahriar_manzoor
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
by Per
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
by shamim
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
by shahriar_manzoor
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...