[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?
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/
Re: Help with Geometric Median formula
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.
Re: Help with Geometric Median formula
Quote:
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...
Re: Help with Geometric Median formula
Quote:
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.
Re: Help with Geometric Median formula
It'll be instantaneous :D
Re: Help with Geometric Median formula
Quote:
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
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.
Sorry about that.
Re: [RESOLVED] Help with Geometric Median formula
Quote:
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.
Sorry about that.
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.