# Is there an algorithm polynomial in dimension of space and number of points for the Minimum Enclosing Ball?

Let $$C_1, ..., C_m \in \mathbb{R}^n$$ Is there a polynomial algorithm in $$n,m$$ which finds the Minimum Enclosing Ball (MEB) for these points?

## My research

I see mentions of algorithms like Megido, Waltz etc. which are known to solve the problem in linear time in $$m$$, the number of points, but these seem to be exponential in $$n$$.

• are you taking Euclidean distances? Apr 5 at 14:52
• There are approximation algorithms based on coresets with polynomial dimension, and there are algorithms with good practical performance on high-dimensional input. But I'm not aware of any exact algorithms with polynomial dependence on the dimension. Are you more interested in theoretical results, or practical performance? Apr 5 at 17:30
• @inuyashaYagami yes, Euclidean distance! Apr 5 at 22:44
• @discreteLizard I am interested in theoretical results! What should be understood by core sets with polynomial dimension? A subset of the points? I would guess that $m$ should be anyway a polynomial w.r.t $n$, otherwise the problem is not approachable in high dimension ! Apr 5 at 22:49
• @CMarius I meant that there are approximation algorithms that use small coresets and have a running time with polynomial dependency on the dimension $n$ (which is usually called $d$ in the literature). For example, [Kumar, P., Mitchell, J. S., & Yildirim, E. A. (2003). Approximate minimum enclosing balls in high dimensions using core-sets.] give a $(1+\varepsilon)$-approximation algorithm that runs in $O(mn/\varepsilon +(1/\varepsilon)^{4.5}\log (1/\varepsilon))$ time for any $\varepsilon>0$. Apr 6 at 8:11