Doesn't the census data record how many live in each location in that block, though?
Not the published data, to my knowledge. I haven't heard of any available redistricting programs that draw lines through individual census blocks, and they probably would if the census bureau made the data available. Whether the census bureau keeps track of that information internally, I don't know.
While in theory it's a knapsack problem you're selecting a very large number of small objects from the knapsack, a degenerate case that shouldn't be NP-hard.
I don't think that helps. Regardless of how you define "close enough to equal" there will be exponentially many combinations right on the border between equal enough and not quite equal enough. In any event, other compactness criteria than yours, such as the "minimize the maximum radius" criterion, have been proven NP-complete by themselves; it would be pretty surprising if the minimum border length criterion were different.
If the problem actually is intractable there's a reasonable shortcut that certainly isn't: Divide the state up into regions using a minimum of boundary area. Consider every pair of adjoining districts--can we move one chunk of population from the district with a higher number of people to the one with a lower number? If so, move the chunk that results in the minimum border area and ends up with a more even result. Go on to the next pair of districts. Repeat until you get through with no moves. This requires defining the order in which the districts are to be compared as you would end up with a different final result if you did your comparisons in a different order.
Aye, there's the rub. You're proposing a greedy algorithm, and those are almost sure to get trapped in local minima when they're used on hard combinatorial problems. But
which local minima? When you no longer have global optimality to protect you, your system becomes susceptible to being gamed. Whichever engineer defines the order of comparisons, or the procedure for discretizing your initial floating-point boundary minimization, or the heuristics used to approximate the minimal unconstrained boundary length in the first place, (assuming that problem is NP-complete which it probably is), or any number of other practical engineering decisions that will go into creating the official district-drawing program, will have an enormous variety of options for making all those decisions. However he makes the decisions, he will of course come up with a perfectly reasonable-sounding story for why they went the way they did. But what assurance can the rest of us have that he didn't write forty different versions of his program, test them all, pick whichever one gave the best results for his party or for his favorite legislator, and then quietly delete the other thirty-nine before announcing that the software was ready?
I understand that you see it as a feature, not a bug, because racial gerrymandering opens the door to corrupt self-dealing design of safe seats for incumbents. But the Supreme Court will see a 30% black state with an all-white legislature as a bug, not a feature. Unless you can reprogram the Supreme Court, your computer's output won't be implemented. Simply abolishing geographical districts is a better solution.
It
is the design of safe seats for members of the group thus protected, 100% pure gerrymandering. I don't believe you can divide gerrymandering into good and bad.
I meant safe seats for identifiable individuals, but if you want to expand the concept, suit yourself. Your legality problem remains.
And note that it would only result in a 30% black state with a pure white government if something like 2/3 of the whites were voting on purely racial lines. If this actually happened Obama would not have been elected.
That doesn't follow at all. All that would need to happen to get an all-white legislature is a state with a solid overall Republican voting majority, plus the district boundaries being unrelated to party preference contour lines and therefore typically more or less orthogonal to them, thus resulting in no Democrat-majority districts, much like picture 2 in post #51 --
plus all the black would-be-legislators choosing to run as Democrats. When the SCOTUS decided racial gerrymandering was necessary in order to let black voters elect black legislators, they weren't being idiots. They were looking at the numbers.
Abolish the districts. Then if the black voters want to mostly vote along racial lines and get black representatives, they'll be able to. But if they instead decide color doesn't matter, and they'd rather split up and ally themselves respectively with white free-traders or with white protectionists, and elect one free-trader legislator and one protectionist legislator of whatever color, they'll be able to do that too. That's how representation is supposed to work.
