Comment Re:xkcd (Score 1) 338
To me a fairly simple solution would be all boundaries (except for those on the edge of the state) must be convex.
You DO realize that any convex boundary is a concave boundary for the district across the boundary, right?
No, that is not necessarily correct, for example a straight line will split a rectangle into two convex polygons.
If you look at what a Voronoi Diagram is, it is a method for subdividing the plane into convex polygons.