Given a situation like this:

enter image description here

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:

enter image description here

So given the example above, the desired output would probably look like this:

enter image description here

Is there an algorithm to calculate this?

  • 1
    K-means algorithm?
    – wilx
    Feb 27, 2017 at 14:11

1 Answer 1


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. Apr 9, 2017 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.