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
----
Election-Methods mailing list - see http://electorama.com/em for list info
