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
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
