Skip to main content
Took the liberty of removing soft-question tag, which does not seem consistent with other uses of that tag. And added algorithms.
Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Source Link
Dan Brumleve
  • 2.3k
  • 17
  • 28

What is the most general class of metric spaces for which the closest pair of points in a finite subset can be found in time O(n^(1+eps))?

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?