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 we开发者_运维问答re 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.

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.

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.