[EM] Breakthrough in political districting algorithms (I think)

[Michael Rouse]

Wow, I haven't thought about space-filling curves for awhile! :)

Back in 1996, I came up with a couple of space-filling curves for the 
Fractint L-system. The first one is somewhat similar to Gosper's 
Flowsnake, but more jagged. I called it Hextar (hexagonal star). The 
second one combined 3 Hextar curves into a closed loop, and in a fit of 
creativity I called it Hexter 2.

I'm not sure if you have access to something that will run L-system 
files, but here are the instructions for both curves (I kept the 
comments intact):

Hextar1 { ; "Hexagonal Star 1" by Michael A. Rouse, 1996
angle 6
axiom s ; to make things start at
s=L     ; order 1
L=LzfR--fR-f++Lf++L-f+Lf+R--y
R=z++L-fR-f+R--fR--f+Lf++LfyR
z=-
y=+
}

Hextar2 { ; "Hexagonal Star 2" ; by Michael A. Rouse, 1996
angle 6
axiom s ; to make things start at
s=Lf++Lf++Lf     ; order 1
L=LzfR--fR-f++Lf++L-f+Lf+R--y
R=z++L-fR-f+R--fR--f+Lf++LfyR
z=-
y=+
}

No clue at all if these will yield any different results from Gosper's 
Flowsnake, though. If you can't run L-system files but would like to see 
them, I can create an image to show you what they look like, from 
order-1 to whatever you want.

Michael Rouse


On 7/17/2011 11:51 AM, Warren Smith wrote:
> http://rangevoting.org/SpaceFillCurve.html
>
> describes a new, incredibly simple, algorithm for political
> districting which is guaranteed to
> get within a constant factor (namely 6.34) of the cost of the optimum
> districting,
> using the cost measure
>     sum(over all people) (distance to their district centerpoint)^2.
>
> Its output can be fed into further optimizers... but my point is
> that no previous polynomial-time algorithm had
> ever been able to guarantee being at most
> any constant factor worse than optimal.
>
> I hope this paper is not insane -- it seems almost too good+simple to be true.
> Email me your questions, comments, complaints, etc about the paper.
>
> (I am also working on a much more complicated polytime algorithm which
> if it pans out will be able to guarantee 1+epsilon approximation...)
>