[EM] Re: Compactness
Joe Weinstein
jweins123 at hotmail.com
Tue Jan 20 17:31:03 PST 2004
Hi Ernie,
In my previous message I stated three points in favor of
distance-compactness (DC) over boundary-compactness (BC). The most
important of these was Forest's point (1) that the very definition of 'the'
boundary between two districts, or even between two neighboring 'atoms' of
districts, is often inherently ambiguous.
However, after posting the message I started wondering whether I got carried
away on my point (3) as to supposed advantage of DC over BC in computation.
So I’ve since tried to subject raw intuition to a bit of precision and
reality check.
Having done so to a point, perhaps not enough, I must revise what I implied,
and go halfway to your position.
Very likely, in your context, BC is easier to handle than DC, or anyhow is
no harder to handle. It sounds like you have a good algorithm, and for good
reasons.
On the other hand (details below) there seems to be just about equally good
news from the DC side too, at least if DC uses squared distance.
Details now follow.
First, some terminology. Let T be the number of census tracts or other
‘atoms’ to assign to S seats or ‘districts’. Assume that the atoms have
been coded into the consecutive numbering, 1 through T, and likewise the
districts. Then a districting plan P is a function which to each integer in
the range 1 through T assigns an integer in the range 1 through S; or
equivalently is a T-tuple of integer entries, each in the range 1 through S.
For purposes of evaluating any plan P, we need various fixed data, in
particular a T-tuple which gives each atom’s population.
Moreover, for purposes of DC we will need for each of the T atoms its
centroidal X and Y coordinates: that’s 2T data.
For purposes of BC we will need for each atom-pair its ‘boundary length’.
That’s roughly T^2/2 data if we sloppily code this info as a sparse TxT
matrix. Of course, we could smartly condense the info in this matrix into a
list of triples, one triple for each nonzero boundary between a pair of
adjoining atoms. I think my intuition went wrong mainly in that I
overlooked this very elementary fact and its potentialities.
Euler’s polyhedral formula (v-e+f=2) implies that the number of such nonzero
boundaries is not too big: approximately, but always less than, 3T, no
matter how regular or irregular may be the configuration of atoms. For each
of these boundaries, we need store just three numbers: the IDs of both atoms
plus the boundary value.
So, the two methods seem to require on the order of the same amount of info.
What about amount of processing?
Well, the answer there seems to depend on to what extent it is economical in
time to pre-calculate and pre-process the info into tables which - for
evaluating plan after plan - are faster to deal with.
That answer in turn will depend partly on stuff with which I am not now
(even if I ever was) sufficiently familiar: on just how fast (in various
instances, for various table sizes and calculation routines and hardware and
software) table lookup can be vs. calculations on the fly. For instance,
for all I know about the comparative timing, in some cases DC calculation
may go faster if we pre-calculate distances into a TxT matrix, and then look
up these values for each new plan.
The answer will also depend on whether we are generating and testing, one
after another, lots of essentially different plans - as versus, instead,
testing variants and small modifications of a given initial plan P. This
latter case, which apparently is your focus, is relevant if we have good
heuristics to suggest a fairly superior but not obviously optimal initial
plan P.
In this latter case especially, it would pay to pre-process the
specification of plan P into convenient supplementary tables. In
particular, one could prepare a list L of 5-tuples, one for each of the at
most 3T boundaries. Each 5-tuple would list not only the three data in the
boundary’s triple, but also the two atoms’ current district IDs. Then, a
small change in plan P would require but small changes in L, and an easy
pass through L would readily sum the boundary values for different-district
atom pairs - or, even faster, would get the complementary sum of all values
for same-district pairs.
But there is good news from the DC side too, if the compactness criterion be
to minimize the average SQUARED distance between same-district atom pairs.
This criterion amounts to minimizing average within-district atom-centroid
squared distance, alias average district (moment of) inertia. It turns out
that one can readily account for small changes in districts by storing and
updating for each district the X- and Y- components both of its centroid and
of its inertia. (Thanks to Pythagoras, the X- and Y- inertias sum to the
total inertia.) For those who want a named theorem behind the technique,
it’s the Parallel Axis Theorem. Years ago I saw a programmer’s writeup of
the one-dimensional analog: for the sake of scratch-memory conservation, he
calculated the mean and variance of a sequence of read-in numbers, by
updating simultaneously the running mean and running variance.
Anyhow, Ernie, I do not doubt that you have an excellent algorithm for
updating the BC effect of small changes in the districting plan, and I thank
you for your corrective!
Joe Weinstein
_________________________________________________________________
There are now three new levels of MSN Hotmail Extra Storage! Learn more.
http://join.msn.com/?pgmarket=en-us&page=hotmail/es2&ST=1
More information about the Election-Methods
mailing list