[jwp]

My intuition says it's not possible to get 1 without destroying the ability to get 2, or vice versa. But I'm no expert. The solution that leaps to my mind is to use a locality-sensitive hash function. It would make search stochastic, which means reversing the encoding would be easier. Seems like any hash-based solution will involve a tradeoff between 1 and 2.

What did you have in mind?

[cmars232]

I still haven't worked out the protocols for matching encoded locations -- hopefully it is possible. I fear you're right, I may not be able to get beyond a simple challenge-response type of comparison without disclosing some information.

Cool thing is, since I got interested in solving this problem, I've learned how R-Trees work! :)

http://en.wikipedia.org/wiki/Hilbert_R-tree