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

[Jameson Quinn]

Nice.

Note that one algorithm for simple database proximity queries using a
one-dimensional index for two-dimensional space, is called geohashing, and
it uses the fractal Z "curve". For my work, I've implemented an optimization
of this, which stores each location three times, in three coordinate systems
which are (toroidally) offset by 1/3 of the total dimensions. Aside from the
north and south poles counting as "adjacent" in this system, it works quite
well for quickly finding a set of N points which are among the nearest. If
you are interested in hearing more (sorry, I realize I'm not sufficiently
explaining this), just ask.

JQ

2011/7/17 Warren Smith <warren.wds at gmail.com>

> 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...)
>
> --
> Warren D. Smith
> http://RangeVoting.org  <-- add your endorsement (by clicking
> "endorse" as 1st step)
> and
> math.temple.edu/~wds/homepage/works.html
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110717/b16398d9/attachment-0004.htm>