3
$\begingroup$

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$.

Improve this question
$\endgroup$
7
  • $\begingroup$ are you taking Euclidean distances? $\endgroup$
    – Inuyasha Yagami
    Apr 5 at 14:52
  • 1
    $\begingroup$ 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? $\endgroup$
    – Discrete lizard ♦
    Apr 5 at 17:30
  • $\begingroup$ @inuyashaYagami yes, Euclidean distance! $\endgroup$
    – C Marius
    Apr 5 at 22:44
  • $\begingroup$ @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 ! $\endgroup$
    – C Marius
    Apr 5 at 22:49
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Discrete lizard ♦
    Apr 6 at 8:11

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.