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

CC BY-SA 4.0
2019-06-19T15:34:50.093Z
I suspect this is hard. This paper has an algorithm with running time roughly $O(k^{O(d)} n\log n)$ http://jeffe.cs.illinois.edu/pubs/pdf/small.pdf
Sasho Nikolov
CC BY-SA 4.0
2019-06-24T04:37:19.510Z
@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.
Jeffε
CC BY-SA 4.0
2019-06-24T05:25:48.587Z
@Jeffε if you turn into a (sourced) answer, I'll be happy to accept!
Aryeh
CC BY-SA 4.0
2019-06-24T05:26:16.673Z
Although I'm *also* interested in various heuristics used in practice.
Aryeh
<computational-geometry>
$\ell_\infty$ partially enclosing ball problem
Aryeh
# $\ell_\infty$ partially enclosing ball problem

(Asked by: username_0 on 2019-06-19)

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?

**Tags:** computational-geometry
> **Comments:**
> **username_1**: I suspect this is hard. This paper has an algorithm with running time roughly $O(k^{O(d)} n\log n)$ http://jeffe.cs.illinois.edu/pubs/pdf/small.pdf  
> **username_2**: @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.  
> **username_0**: @Jeffε if you turn into a (sourced) answer, I'll be happy to accept!  
> **username_0**: Although I'm *also* interested in various heuristics used in practice.  

---

## 0 answers

