A faster dual algorithm for the Euclidean minimum covering ball problem

Abstract

Dearing and Zeck presented a dual algorithm for the problem of the minimum covering ball in ${\mathbb{R}}^n$. Each iteration of their algorithm has a computational complexity of at least $\mathcal{O}(n^3)$. In this paper we propose a modification to their algorithm that, together with an implementation that uses updates to the QR factorization of a suitable matrix, achieves a $\mathcal{O}(n^2)$ iteration.

Latex; 12 pages; typo corrected