0

It is the following question with the points instead of lying in a 2D plane, are located in a higher dimensional space: Choose the closest k points from given n points.

What is known about the above problem? If it is NP-hard then what is the best approximation ratio known and any lower bounds?

Pawan Aurora
  • 113
  • 4
  • In a high dimension space I would expect that the curse of dimensionality makes the naive algorithm best. Also I would not expect to find `k` points very close to each other. – btilly Jul 28 '20 at 19:51
  • @btilly does it help if we know that all the n points can be confined inside a sphere of radius c/\sqrt{n} for some constant c? Also k=\sqrt{n}. – Pawan Aurora Jul 30 '20 at 07:17

0 Answers0