## 10228 - Star not a Tree?

Moderator: Board moderators

Shahab
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm

### 10228 - Star not a Tree?

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.

Trickster
New poster
Posts: 6
Joined: Sat Sep 20, 2003 6:31 am
Location: Recife, Brazil

### 10228 - A star not a tree?

Hi everyone,

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!

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

iggy
New poster
Posts: 3
Joined: Mon May 05, 2008 10:44 am

### Re: 10228 - A Star not A Tree

Gradient descent with centroid as a starting point works well too.
Is there a geometrical solution though?