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?