I wonder if the coastline paradox might be a factor. You’d get disagreements about the true length of certain boundaries.
Here’s a map which shows explicitly that Houston’s nine Congressional districts included five with 2002 Democratic vote of at least 43%, but only three after boundaries were redrawn. That map is from an interesting article which gives further examples of egregious Texas gerrymandering, and proposes an automatic tamper-proof districting algorithm.
(I’m not sure there is any simple antidote to the gerrymandering problem. After all, grouping similar people together has merit – at there other extreme, the districts in a state with 52-48 party split would all have 52-48 split, and only one party would be elected.)
It’s an interesting approach. But certainly not a perfect one. Look at this map from their website and how they point out how Austin was divided up between three districts to put its citizens in a majority in each of those districts.
Now look at their proposed map for Arkansas. Guess what’s located at the intersection of those four districts? The Little Rock metropolitan area. Like Austin, Little Rock just had its voters split up among several different mostly rural districts. (And just so you don’t think this is a fluke, their plan would do the same thing with Albuquerque in New Mexico.)
It shouldn’t be a problem. Boundaries established by humans aren’t generally exactly along natural features like rivers or coastlines: Usually, they’re straight lines or simple curves between benchmarks, so as to approximate the natural features. You can specify boundaries that are arbitrarily or even infinitely long, but in this scenario the map-makers are trying to make boundaries that are as short as possible, so they naturally wouldn’t do that.