Optimization Online


A faster dual algorithm for the Euclidean minimum covering ball problem

Marta Cavaleiro(marta.cavaleiro***at***rutgers.edu)
Farid Alizadeh(farid.alizadeh***at***rutgers.edu)

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.

Keywords: minimum covering ball, smallest enclosing ball, 1-center, minmax location, computational geometry

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: June 2017

Download: [PDF]

Entry Submitted: 06/30/2017
Entry Accepted: 06/30/2017
Entry Last Modified: 06/30/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society