Brown CS k-means Redistricting

K-Means redistricting at Brown U
https://news.brown.edu/articles/2017/11/redistricting

I tried this 10 years ago and it's fast and simple but it isn't good enough.

The solver in the article seems to completely ignore existing boundaries including the boundaries to which the Census has actually counted data called 'blocks' (sometimes a city block, sometimes an empty square mile of Montana). If they're assuming that population is fungible and uniformly distributed within a Census block I think that's invalid. My k-means solver drew those nice straight lines but then assigned whole blocks based on whether the center of the block was one side of the line or the other. All the districts thus had ragged edges.

Because the k-means algorithm has very few data points to fiddle (district center, district weight) it can't find complex solutions. When I ran a k-means solver it couldn't find districts with close enough to equal population in a few places.

I eventually went with a solver that considered one at a time each block on a border of two districts to see if a block would be better moved to the other district. That kind of detail and flexibility made maps that weren't as ideally simple, but still had good compactness, had much better equal-population constraint satisfaction, and should be much more workable for observing the same Census blocks that existing redistricting is done on.