(1b) I have an n*lg(n) solution for 2-D. Sorry, BrowserUK: I was SO wrong in saying no tree. My solution (which I have not coded) uses a PR quadtree. My solution is certainly not the only approach that will work.

(1c) I have no idea (yet) how this might be brought up to O(n), nor do I have a clue (yet) how to prove it impossible.

(2a) Also, while a PR quadtree can be used in 3D, my approach does not extend easily to 3D. More thought required.

Question: For a puzzle, ought I post pseudocode/code on completion, or is it polite to instead leave the solution unposted, giving others the fun of solving it?

Keep chuggin', guys! Nothing quite so rewarding as solving a tough puzzle!