What is the most general class of metric spaces for which the closest pair of points in any finite subset can be found in time O(n^(1+eps))? I have studied how to do this in O(n log(n)) in the plane, and I believe I can generalize the same method to some other surfaces, but it does not work in 3-space (maybe it is possible but I suspect not). Are there any interesting examples of metric spaces in which this problem can be solved efficiently?
Took the liberty of removing soft-question tag, which does not seem consistent with other uses of that tag. And added algorithms.
Joseph O'Rourke
- 150.8k
- 36
- 358
- 958