Suppose I have $n$ points in $\mathbb{R}^d$ endowed with the $\ell_\infty$ metric, and I wish to find a minimum-diameter ball that contains some $k$ of these points. What is known about this problem? Easy/hard? Approximations? Heuristics?

  • 4
    $\begingroup$ I suspect this is hard. This paper has an algorithm with running time roughly $O(k^{O(d)} n\log n)$ jeffe.cs.illinois.edu/pubs/pdf/small.pdf $\endgroup$ – Sasho Nikolov Jun 19 at 15:34
  • 2
    $\begingroup$ @SashoNikolov is correct. Every n-vertex graph is the intersection graph of O(n)-dimensional unit hypercubes. Thus, in sufficiently high dimensions, this problem is equivalent to deciding whether a given graph contains a k-clique. $\endgroup$ – Jeffε Jun 24 at 4:37
  • $\begingroup$ @Jeffε if you turn into a (sourced) answer, I'll be happy to accept! $\endgroup$ – Aryeh Jun 24 at 5:25
  • $\begingroup$ Although I'm also interested in various heuristics used in practice. $\endgroup$ – Aryeh Jun 24 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.