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