Nice. <div><br></div><div>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.</div>

<div><br></div><div>JQ<br><br><div class="gmail_quote">2011/7/17 Warren Smith <span dir="ltr"><<a href="mailto:warren.wds@gmail.com">warren.wds@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<a href="http://rangevoting.org/SpaceFillCurve.html" target="_blank">http://rangevoting.org/SpaceFillCurve.html</a><br>
<br>
describes a new, incredibly simple, algorithm for political<br>
districting which is guaranteed to<br>
get within a constant factor (namely 6.34) of the cost of the optimum<br>
districting,<br>
using the cost measure<br>
   sum(over all people) (distance to their district centerpoint)^2.<br>
<br>
Its output can be fed into further optimizers... but my point is<br>
that no previous polynomial-time algorithm had<br>
ever been able to guarantee being at most<br>
any constant factor worse than optimal.<br>
<br>
I hope this paper is not insane -- it seems almost too good+simple to be true.<br>
Email me your questions, comments, complaints, etc about the paper.<br>
<br>
(I am also working on a much more complicated polytime algorithm which<br>
if it pans out will be able to guarantee 1+epsilon approximation...)<br>
<font color="#888888"><br>
--<br>
Warren D. Smith<br>
<a href="http://RangeVoting.org" target="_blank">http://RangeVoting.org</a>  <-- add your endorsement (by clicking<br>
"endorse" as 1st step)<br>
and<br>
<a href="http://math.temple.edu/~wds/homepage/works.html" target="_blank">math.temple.edu/~wds/homepage/works.html</a><br>
</font></blockquote></div><br></div>