Approximate minimum enclosing balls in high dimensions using core-sets

DOI10.1145/996546.996548zbMath1083.68138OpenAlexW2029494882MaRDI QIDQ5463443

E. Alper Yıldırım, Joseph S. B. Mitchell, Piyush Kumar

Publication date: 4 August 2005

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/jea/2003/KumarComputing/

zbMATH Keywords

algorithmsapproximation algorithmssecond-order cone programmingminimum enclosing ballcore sets

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries, Linear-size universal discretization of geometric center-based problems in fixed dimensions, A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems, On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids, New algorithms for \(k\)-center and extensions, A branch-and-bound method for the minimum \(k\)-enclosing ball problem, Polynomial time approximation schemes for all 1-center problems on metric rational set similarities, Streaming and dynamic algorithms for minimum enclosing balls in high dimensions, Multi-view L2-SVM and its multi-view core vector machine, Scalable learning method for feedforward neural networks using minimal-enclosing-ball approximation, A new algorithm for the minimax location problem with the closest distance, Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space, Unnamed Item, On the string consensus problem and the Manhattan sequence consensus problem, Frank-Wolfe and friends: a journey into projection-free first-order optimization methods, FRSDE: Fast reduced set density estimator using minimal enclosing ball approximation, Analysis of incomplete data and an intrinsic-dimension Helly theorem, Optimal core-sets for balls, Computing minimum-volume enclosing axis-aligned ellipsoids, Minimal containment under homothetics: a simple cutting plane approach, On a minimum enclosing ball of a collection of linear subspaces, Practical methods for shape fitting and kinetic data structures using coresets, A dual simplex-type algorithm for the smallest enclosing ball of balls, Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions, Unnamed Item, Streaming algorithms for extent problems in high dimensions, Complexity and approximation of the smallest \(k\)-enclosing ball problem, Minimum-volume enclosing ellipsoids and core sets

Uses Software

• SeDuMi
• SDPT3
• Miniball

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving semidefinite-quadratic-linear programs using SDPT3
• Approximating the diameter of a set of points in the Euclidean space
• Applications of second-order cone programming
• Second-order cone programming
• Solution methodologies for the smallest enclosing circle problem
• A Mathematical View of Interior-Point Methods in Convex Optimization
• Warm-Start Strategies in Interior-Point Methods for Linear Programming
• Extensions of Lipschitz mappings into a Hilbert space
• Approximate clustering via core-sets
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Primal-Dual Interior-Point Methods for Self-Scaled Cones
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• An efficient, exact, and generic quadratic programming solver for geometric optimization
• Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus
• The smallest enclosing ball of balls
• The Minimum Covering Sphere Problem
• Algorithms - ESA 2003
• Choosing multiple parameters for support vector machines