I need to split up an area into non-overlapping, but contiguous territories. I have n points on a map, which are partitioned into k sets. The partition is only partially geographic, meaning that there is no reason to believe that the points are mixed in with one another. No two points overlap each other. The problem is to draw polygons such that each polygon contains all points from one set, and excludes all points from all other sets, such that the polygons have the following properties: No two polygons overlap each other. Polygons must be contiguous.

A further "nice to have" would be that the polygons minimise the proportion of the area they cover which is not within r distance units of any of the points in the set, subject to the condition that no two lines of the polygon are closer than d to each other.

I can't post an image of what I'm talking about until I have reputation 10. Please let me know if what I'm asking is unclear.

My question is this: Has anything like this been done before? Are there any papers I should be reading, or known algorithms I can make use of? I'm new to GIS in general, are there any suggestions on search terms I could be using to find similiar concepts?


  • How come you drew the polygon the way you did? You could just as easily drawn the red one to go through Brits and Hartbeespoort between the blue points and combine the two blue points near Brits with the other two north of Mooinooi. Also, you could have connected the Secunda point with the ones near Katlehong instead of the ones near Emalahleni. I'm just trying to understand how you came about your polygons. – Fezter Apr 29 '13 at 1:16
  • Hi Fetzer. My first guess is to draw the minimum spanning trees of each set, and then modify the trees so as to remove crossings. So, I imagine the MST for the blue set would pass from Brits to Mooinooi, and the red MST would cross it, joining the isolated point to Pretoria. Because the red edge is the longer, I modify it by adding in artificial red points North of the isolated red point, until such time that the MST's no longer cross one another. That's what I had in mind when I drew the polygons, and so what I drew is my expected outcome of that. Your linking is better. – CPhil May 9 '13 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.