# Clustering of points that minimizes overall average distance to given center

Given a situation like this: where the position of the triangles is given (it does not need to be calculated by an algorithm). I would like to find clusters of circles around the triangles. Each cluster should contain a given number of circles (in this example every cluster gets 4 circles) and the clusters should be formed in such a way that the average of the average distances from the center of each triangle to the center of every circle in its cluster is minimal. In mathematical notation, the goal is to minimize the value: So given the example above, the desired output would probably look like this: Is there an algorithm to calculate this?

• K-means algorithm? – wilx Feb 27 '17 at 14:11

## 1 Answer

What you are describing is close to a K-means.

But (classic) K-means is based on square of the distance and cluster size is not fixed. So you would need to adjust your criteria to comply with K-means or modify the algorithm.

If you don't want to take the distance squared the algorithm gets more complex.

• Thanks for pointing me in the right direction. I solved the problem by applying first one clustering step of K-means, so that circles get assigned to the closest triangle, and then depending on the number of circles assigned to each triangle I reassigned circles to other triangles until the number of circles assigned to a triangle satisfy the given condition. – Carlos Rodriguez Apr 9 '17 at 18:16