Results 1 to 10 of 10

Thread: [RESOLVED] Help with Geometric Median formula

  1. #1

    Thread Starter
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    24,072

    Resolved [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?

  2. #2

    Thread Starter
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    24,072

    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/

  3. #3
    Fanatic Member Delaney's Avatar
    Join Date
    Nov 2019
    Location
    Paris, France
    Posts
    648

    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)

  4. #4
    Frenzied Member
    Join Date
    Nov 2017
    Posts
    1,646

    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.

  5. #5

    Thread Starter
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    24,072

    Re: Help with Geometric Median formula

    Quote Originally Posted by OptionBase1 View Post
    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...

  6. #6
    Frenzied Member
    Join Date
    Nov 2017
    Posts
    1,646

    Re: Help with Geometric Median formula

    Quote Originally Posted by .paul. View Post
    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.

  7. #7

    Thread Starter
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    24,072

    Re: Help with Geometric Median formula

    It'll be instantaneous

  8. #8
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,170

    Re: Help with Geometric Median formula

    Quote Originally Posted by OptionBase1 View Post
    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

  9. #9
    Frenzied Member
    Join Date
    Nov 2017
    Posts
    1,646

    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.

  10. #10
    Frenzied Member
    Join Date
    Nov 2017
    Posts
    1,646

    Re: [RESOLVED] Help with Geometric Median formula

    Quote Originally Posted by OptionBase1 View Post
    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
  •  



Click Here to Expand Forum to Full Width