Any idea to solve such a problem, plz?
I have the idea of derivation of the sum of the distances, but it is really hard and unamusing to code.
Thanks in advance
10228  Star not a Tree?
Moderator: Board moderators
10228  A star not a tree?
Hi everyone,
i
i
"There's a difference between knowing the path, and walking the path."

 New poster
 Posts: 5
 Joined: Tue Jun 14, 2005 7:12 pm
Hi,
I know this is an old post, but maybe this will still be helpful. Your method is incorrect. Using the centroid will not give the minimum value for the sum of all the distances. (It might be for the sum of the squares of the distances... I would have to think about it more).
How is your multivariate calculus? Think of how you can form a system of 2 equations over two unknowns f(x,y)=0 and g(x,y)=0 where (x,y) represents the location of the hub. Then look up some methods on solving these systems numerically (i.e. not necessarily an exact solution, but close enough for what the problem asks for). The centroid is a good initial approximation for a numerical method, but not the solution. I had my solution accepted on the first try.
Good Luck!
I know this is an old post, but maybe this will still be helpful. Your method is incorrect. Using the centroid will not give the minimum value for the sum of all the distances. (It might be for the sum of the squares of the distances... I would have to think about it more).
How is your multivariate calculus? Think of how you can form a system of 2 equations over two unknowns f(x,y)=0 and g(x,y)=0 where (x,y) represents the location of the hub. Then look up some methods on solving these systems numerically (i.e. not necessarily an exact solution, but close enough for what the problem asks for). The centroid is a good initial approximation for a numerical method, but not the solution. I had my solution accepted on the first try.
Good Luck!

 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact:
Re: 10228  A Star not A Tree
Gradient descent with centroid as a starting point works well too.
Is there a geometrical solution though?
Is there a geometrical solution though?