Optimization Online


Identification and Elimination of Interior Points for the Minimum Enclosing Ball Problem

S. Damla AHIPASAOGLU (dse8***at***cornell.edu)
E. Alper YILDIRIM (yildirim***at***bilkent.edu.tr)

Abstract: Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of $\cA$. In this note, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in $\cA$ that are guaranteed to lie in the interior of the minimum-radius ball enclosing $\cA$. Our computational results reveal that incorporating this procedure into the two recent algorithms proposed by \Yildirim~leads to significant speed-ups in running times especially for randomly generated large-scale problems. We also illustrate that the extra overhead due to the elimination procedure remains at an acceptable level for spherical or almost spherical input sets.

Keywords: Minimum enclosing balls, input set reduction, approximation algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: SIAM J. Optim. Volume 19, Issue 3, pp. 1392-1396 (2008)

Download: [PDF]

Entry Submitted: 08/19/2008
Entry Accepted: 08/19/2008
Entry Last Modified: 11/25/2016

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