CODEWITHSUNDEEP
algorithmcoordinatescartesian
Kasper Holdum
Kasper Holdum

Reputation: 13363

Place N Point to Minimize Distance to a List of Points

Given a list of points on a 2D plane how could one place N points on the plane in such a way that that the total sum of all distances from the list of points to the closest placed point were as small as possible? The environment is discreet and the list will contain unique points within a range of [(0,0) ; (~200:~100)]

Preferably the algorithm's worst case performance should be polynomial (and thus with the small ranges computational in real time). Any approximations are welcome as well.

Upvotes: 3

Views: 1205

Answers (2)

Yochai Timmer
Yochai Timmer

Reputation: 49251

You could get the Center of mass of the list of nodes (with weights = 1).
Or a variance of it with x^2 for distances.

You've reduced the problem to where to place the N nodes in the area of center of mass where the distance to the rest is minimal.

In a perfect world you'd just put one point in the center of mass. But because I assume you can't place 2 points in the same place, you need to choose the vicinity of the center of mass.

So that reduces the problem to just choosing the best of 8 points near the center of mass, then recalculate center of mass, and do it again.

Upvotes: 0

zw324
zw324

Reputation: 27180

This sound really like what K-Means clustering algorithm do. In your case, the list of points are the input, and the number of points N is the number of clusters.

Sadly, what it does is NP-hard. But there are many researches going on, and a lot ways to try to make it better (just scroll down the wiki page you'll find some).

Also, I doubt there will be a better algorithm, since k-means is really heavily used by academics. I guess if there is a better algorithm they'd run for that one:)

And again, I present you the best tutorial in Data Mining for me: Andrew Moore's slides. Although I don't know your purpose, this should be very close to what you need.

Upvotes: 3

Related Questions