bisection or something else..

Let's talk about algorithms!

Moderator: Board moderators

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

bisection or something else..

Post by sohel » 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?

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » 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
:D
"Life is more beautiful with algorithm"

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » 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 !!

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Mon Apr 24, 2006 8:26 am

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
"Life is more beautiful with algorithm"

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » 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? ;)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Apr 25, 2006 7:15 am

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. :)

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Apr 25, 2006 9:23 am

The superset of this problem exists in UVa:

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

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Apr 25, 2006 9:25 am

Another harder version exists in Dhaka regional 2002, although both may have small floating point problem.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Apr 25, 2006 9:53 am

Also a somewhat similar problem is :)

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » 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.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » 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.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » 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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » 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.)

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Re: hmm

Post by shamim » 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.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » 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...

Post Reply

Return to “Algorithms”