We're about an automated districting tool. We want to create Y districts from X polygons, all having a specific value (e.g. area or inhabitants), where the total value of each district is as similar as possible and each district is also as similar as possible. Let's call the value the "potential".
That's actually a really good problem. I don't know of any canned algorithms for this particular problem, however. You could probably look at it as a special case of graph partitioning where you're weighting vertices and have the constraint that all vertices have roughly the same weight. This is somewhat related to flow algorithms (a partition is a cut). Another view would be to generate a hypergraph (which the BGL doesn't natively support) such that each hyperedge is a set of combined districts. You could write some algorithm that selected a set of disjoint hyperedges all of similar weight. Hope that help, Andrew Sutton andrew.n.sutton@gmail.com