I have a map of stores for a retailer. I am trying to form clusters (of these stores) such that each member of a cluster is at most 5km away from any other member and any non-member is at least 10 km from any member. I also would like to create a field in the point dataset indicating to which cluster a specific store beongs to. What would be the easiest way to do this? Thanks

  • 3
    This problem needs to be framed differently, because its objectives can be contradictory. E.g., what would be a solution for two stores that are 8 km apart? They can't be part of the same cluster but they can't be put into separate clusters.
    – whuber
    Oct 31, 2011 at 19:37
  • maybe single stores 8km apart are in their own group.
    – Brad Nesom
    Oct 31, 2011 at 19:54
  • 2
    @Brad Putting stores 8 km apart into a group violates the first criterion. I gave only the simplest example of the internal contradictions. What would be done with 3 stores spaced 4 km apart on a line, for instance? Or with a bunch of stores spaced along the perimeter of a 4 km radius circle around another store?
    – whuber
    Oct 31, 2011 at 21:28
  • umut, IMHO it's a good idea to sketch (with paper and pencil) the clustering criteria, that will certainly help you to reach a better approach. Also, look for some clustering theory (en.wikipedia.org/wiki/Cluster_analysis) to understand the machine's interpretation of clusters.
    – Pablo
    Nov 1, 2011 at 15:16

1 Answer 1


As @whuber says, I think you're going to need to relax your criteria, because it won't work as stands. One possible algorithm would be:

  • for each point calculate the distance to the nearest other point - in Mapinfo this can be done using the Distance Calculator tool, or in MapBasic
  • arrange these distances in descending order
  • for the smallest nearest distance, select all points that are within 5km (or whatever parameter you choose) of that point -
  • draw a convex hull around these points (a shape that encloses all points)
  • remove those points from the list and continue down the descending list of nearest distances, only selecting those points which have not already been made into a convex hull

There are automated routines to do this sort of analysis in packages like ArcGIS or R, but processing time will be significant if you have a large number of points. You will probably have to experiment to get the best results, I don't think it's possible to lay down hard rules about clusters as you have above.

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.