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

[Raph Frank]

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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20091118/c111383e/attachment-0003.htm>