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