
Mar 22nd, 2021, 10:47 PM
#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?
 Coding Examples:
 Features:
 Online Games:
 Compiled Games:

Mar 23rd, 2021, 12:55 AM
#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/geometricmedian/
 Coding Examples:
 Features:
 Online Games:
 Compiled Games:

Mar 23rd, 2021, 04:58 AM
#3
Re: Help with Geometric Median formula
The best friend of any programmer is a search engine
"Don't wish it was easier, wish you were better. Don't wish for less problems, wish for more skills. Don't wish for less challenges, wish for more wisdom" (J. Rohn)
“They did not know it was impossible so they did it” (Mark Twain)

Mar 23rd, 2021, 10:57 AM
#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.

Mar 23rd, 2021, 05:44 PM
#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...
 Coding Examples:
 Features:
 Online Games:
 Compiled Games:

Mar 23rd, 2021, 06:06 PM
#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.

Mar 23rd, 2021, 06:17 PM
#7
Re: Help with Geometric Median formula
It'll be instantaneous
 Coding Examples:
 Features:
 Online Games:
 Compiled Games:

Mar 24th, 2021, 12:13 PM
#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

Mar 24th, 2021, 03:23 PM
#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.
Sorry about that.

Mar 31st, 2021, 12:46 PM
#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.
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.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
