[EM] Another auto districting proposal (Crystal districting?)

[Juho]

This is a nice approach. Maybe it could be simpler though. What do you  
think about using N points and the d^2+kn rule, and determining a  
criterion that tells how good some given division is (taking path  
lengths, equal distribution of voters etc. as parameters), and then  
use any generic optimization algorithms that can modify both the kn  
values and the location of the points to find the best solution based  
on the agreed criterion?

On could either agree one official optimization algorithm and then run  
it, or one could allow anyone to try to optimize the division and then  
officially adopt the best found result to be used in the elections.

Well, this approach is also complex in the sense that the general  
optimization algorithms may be as complex as you want, but the  
optimization algorithms are totally independent of the politics and  
the basic rules that determine what the final outcome should be (the  
criterion) can be quite simple and intuitive.

(Additional criteria like favouring border lines that follow the  
borders of states or rivers etc. can be easily included in the agreed  
criterion. Maybe even higher cost of splitting cities etc.)

Juho



On Nov 18, 2009, at 4:29 PM, Raph Frank wrote:

> Was thinking, what about something like:
>
> 1) Select N*M points on the map "somehow".
> N is the number of seats
> M is a power of 2 (say 256)
>
> 2) Each block is assigned to the point that has the lowest
>
> d^2 + kn
>
> d = distance from block (or person) to point
> kn = offset for that point
>
> 3) Select the kn values so that all points have equal population.
>
> This generates a convex region for each point.
>
> (Hopefully, there is always a unique solution?).
>
> The population difference between the max and min regions would be  
> less than double the size of the max census block (so less than 2   
> (i.e. one or zero), if each resident was considered individually,  
> and they all lived alone).
>
> One issue at this point is that ideally, these blocks should  
> themselves be contiguous.  Depending on how the state boundary goes,  
> this might not occur.  If they aren't contiguous, then the resulting  
> districts wouldn't be guaranteed to be contiguous.  Ofc, this is  
> also true for splitline.
>
> 4) Find the 2 regions such that
> a) they are contiguous
> b) they haven't been combined already in this round
> c) If they split the map into 2 parts, all resulting pieces must  
> still have an even number of regions
> d) they have the best measure of some kind
>
> (also if combining 2 regions will fix a non-contiguous region  
> problem, then they must be given priority?)
>
> 5) Combine those 2 regions into a combined region
>
> 6) Goto 4) unless all regions have been combined in this round
>
> 7) If there are more than N regions remaining, then advance to next  
> round and goto 4)
>
> Notes on the combination rules:
>
> a) they are contiguous
>
> This is obvious
>
> b) they haven't been combined already in this round
>
> Since M is a power of 2, by pairing off all the blocks in each  
> round, after a log2(M) rounds there will be N regions.
>
> c) If they split the map into 2 parts, all resulting pieces must  
> still have an even number of regions
>
> This is to prevent regions ending up locked out and unpairable.
>
> For example, if the regions formed a line
>
> ABCDEFGH
>
> and BC was combined, then A would be isolated.
>
> A--DEFGH
>
> Thus it can't be combined.
>
> This means that the only valid combinations in the example are AB,  
> CD, EF, GH.
>
> Also, it is important that "connected" refers to connections that  
> occur inside the State boundary.  The regions near the edges of the  
> State will extend to infinity, but connections outside the state  
> don't count.
>
> d) they have the best measure of some kind
>
> This should try to combine regions of dense population.
>
> For example,
> - the perimeter when combined (lower better)
> - the distance between their centres of population (lower better)
> - area (low better)
> - Area/(perimeter^2) (high better)
>
> Note on step 1)
>
> I think a fast version of splitline should be sufficient here.  For  
> example, you could alternate between N-S and E-W lines.  Once M*N  
> "boxes" are created, you could take the centre of population of each  
> box as one of the points.
>
> Each step would only require a median search.  There would be no  
> requirement to figure out the intercept point between the lines and  
> the State boundary.  Also, population balance isn't critical here  
> (though can probably achieved).
> ----
> Election-Methods mailing list - see http://electorama.com/em for  
> list info