[EM] Re: Compactness

[Ernest Prabhakar]

Hi Joe,

On Jan 18, 2004, at 8:42 PM, Joe Weinstein wrote:
> However, various writers on districting prefer instead cutely to use 
> an extrinsic and sometimes more complex measure - boundary length.   
> Hitherto, out of a certain feeling of charity, I have tended to regard 
> this substitution as innocuous and acceptable.

I can appreciate that you may consider compactness a more aesthetic and 
politically appropriate choice of district definition.   However, I'm 
not sure why you consider it less complex and more easily computable 
than boundary measures.

> (3)  For the sakes both of conceptual simplicity and of practical 
> computation of a districting plan’s ‘goodness’ or ‘merit’, it’s 
> preferable to define compactness or any other amenable concept 
> intrinsically rather than extrinsically, whenever we can manage to do 
> so.  In particular, it’s a lot simpler to compute just the average, 
> over all SINGLE districts, of the district’s intrinsic sprawl, as 
> versus having to compute the average, over all PAIRS of districts, of 
> the weighted boundary between the pair.

Actually, in my experience, the result is actually the opposite.   Of 
course, I define boundary minimization as minimizing the boundary of 
each district, so I have no idea why one would need to calculate PAIRS. 
  Specifically, for n districts, I can calculate the boundary in order 
(sqrt[n]), since I only  have to sum along the 'edge' districts.   This 
is also amenable to a straightforward iterative process for improving 
district boundaries,  since it is trivial to measure the impact on edge 
length moving one atomic unit from district A to district B.

To do this using a compactness measure requires summing over all 
districts seems to be a computation of order[n], which would be 
costlier than the boundary measure.   Also, this doesn't lead itself 
well to at least a naive minimization solution, since I believe adding 
-any- units to a district would -always- decrease compactness, by most 
measures.

Put another way, I've already come up with a fairly concise and 
efficient way to implement a boundary minimization algorithm, which I 
hope to post in the next day or two.  It seems to me than any 
compactness based measures as you describe would actually be harder and 
more time-consuming to calculate.  Of course,  perhaps you have a 
clever algorithm for generating such districts that I'm not aware of, 
which I'd be very interested in seeing.

Yours,
Ernie P.

> Joe Weinstein
>
> _________________________________________________________________
> High-speed users—be more efficient online with the new MSN Premium 
> Internet Software. 
> http://join.msn.com/?pgmarket=en-us&page=byoa/prem&ST=1
>