# Thread: [RESOLVED] Help with Geometric Median formula

1. ## [RESOLVED] Help with Geometric Median formula

I'm working on calculating a Geometric Median for an array of points...

Dim p() As New Point ={New Point(1,2), New Point(2,2), New Point(3,4), New Point(5,1), New Point(2,1)}

I've found a formula.. at... https://en.wikipedia.org/wiki/Geometric_median
but, I don't know how to convert that into code. Can anyone explain? Also can you recommend somewhere I can test the working algorithm?  Reply With Quote

2. ## Re: Help with Geometric Median formula

I found this, and was able to convert it to VB, but i have no way of testing it more thoroughly...

https://www.geeksforgeeks.org/geometric-median/  Reply With Quote

3. ## Re: Help with Geometric Median formula  Reply With Quote

4. ## Re: Help with Geometric Median formula

How many potential points are you dealing with? As the Wikipedia article points out, there isn't a plug and chug formula for this.

One option is to just brute force it. For each point in the list, calculate the total distance from that point to the other points. Find the point where that total distance is the minimum. As I read it, that is the end goal.  Reply With Quote

5. ## Re: Help with Geometric Median formula Originally Posted by OptionBase1 How many potential points are you dealing with? As the Wikipedia article points out, there isn't a plug and chug formula for this.

One option is to just brute force it. For each point in the list, calculate the total distance from that point to the other points. Find the point where that total distance is the minimum. As I read it, that is the end goal.
Potentially 2 to many points. Ill post the completed app in the code bank, and send you a link, if youre interested in seeing it working...  Reply With Quote

6. ## Re: Help with Geometric Median formula Originally Posted by .paul. Potentially 2 to many points. Ill post the completed app in the code bank, and send you a link, if youre interested in seeing it working...
I keep an eye on the CodeBank threads, so I'll take a look once you post it.

If many could be 1,000,000, then the brute force method is problematic, since for each point you are calculating 1,000,000 distances (the distance from the point being examined to itself is obviously 0), so that is 1 trillion total calculations, which would presumably take a very noticeable amount of time.

If many doesn't get anywhere near that number, like if it is almost always less than 1000, then it should be essentially instantaneous to brute force.  Reply With Quote

7. ## Re: Help with Geometric Median formula

It'll be instantaneous   Reply With Quote

8. ## Re: Help with Geometric Median formula Originally Posted by OptionBase1 How many potential points are you dealing with? As the Wikipedia article points out, there isn't a plug and chug formula for this.

One option is to just brute force it. For each point in the list, calculate the total distance from that point to the other points. Find the point where that total distance is the minimum. As I read it, that is the end goal.
I'm not sure about your description of the brute force method. Suppose, for example, the points are dotted around roughly in a circle. The point which has the smallest total distance to all the other points will still be on or near the circumference of the circle. But the geometric median should be somewhere near the middle of the circle. Or have I misunderstood? BB  Reply With Quote

9. ## Re: [RESOLVED] Help with Geometric Median formula

No, you haven't misunderstood, I did. I was under the mistaken impression that it would need to be a point within the set. After further reading of the Wikipedia page discussing the Geometric Median, that appears to not be the case.  Reply With Quote

10. ## Re: [RESOLVED] Help with Geometric Median formula Originally Posted by OptionBase1 No, you haven't misunderstood, I did. I was under the mistaken impression that it would need to be a point within the set. After further reading of the Wikipedia page discussing the Geometric Median, that appears to not be the case.

Just to add one final note to this, the approach of locating the point in the set such that the total distance to all other points is how the geometric medoid is found.

So, in your program, you could still use this approach, but just change the name in your program to Geometric Medoid rather than Geometric Mean to reflect the proper name of the point that is being returned.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•