creating clusters of point data

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

-
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 '11 at 19:37
maybe single stores 8km apart are in their own group. – Brad Nesom Oct 31 '11 at 19:54
@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 '11 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 '11 at 15:16

1 Answer

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.

-