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$ Commented Jun 19, 2019 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ε
    Commented Jun 24, 2019 at 4:37
  • $\begingroup$ @Jeffε if you turn into a (sourced) answer, I'll be happy to accept! $\endgroup$
    – Aryeh
    Commented Jun 24, 2019 at 5:25
  • $\begingroup$ Although I'm also interested in various heuristics used in practice. $\endgroup$
    – Aryeh
    Commented Jun 24, 2019 at 5:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.