Approximate minimum enclosing balls in high dimensions using core-sets

Piyush Kumar, Joseph S.B. Mitchell, E. Alper Yildirim

Research output: Contribution to journalArticlepeer-review

Abstract

We study the minimum enclosing ball (MEB) problem for sets of points or balls in high dimensions. Using techniques of second-order cone programming and "core-sets", we have developed (1 + ε)-approximation algorithms that perform well in practice, especially for very high dimensions, in addition to having provable guarantees. We prove the existence of core-sets of size O(1/ε), improving the previous bound of O(1/ε2), and we study empirically how the core-set size grows with dimension. We show that our algorithm, which is simple to implement, results in fast computation of nearly optimal solutions for point sets in much higher dimension than previously computable using exact techniques.

Original languageEnglish
Article number996548
JournalACM Journal on Experimental Algorithmics
Volume8
DOIs
Publication statusPublished - 1 Jan 2003

Keywords

  • Approximation algorithms
  • Core-sets
  • F.2.0 [analysis of algorithms and problem complexity]: general - geometrical problems and computations
  • Minimum enclosing ball
  • Second-order cone programming

Fingerprint

Dive into the research topics of 'Approximate minimum enclosing balls in high dimensions using core-sets'. Together they form a unique fingerprint.

Cite this