Approximate minimum enclosing balls in high dimensions using core-sets
From MaRDI portal
Publication:5463443
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/
Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (28)
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
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
This page was built for publication: Approximate minimum enclosing balls in high dimensions using core-sets
