THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS

DOI10.1142/S0218195904001500zbMath1084.68132OpenAlexW2123229994MaRDI QIDQ4824662

Kaspar Fischer, Bernd Gärtner

Publication date: 1 November 2004

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195904001500

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

The log-exponential smoothing technique and Nesterov's accelerated gradient method for generalized Sylvester problems ⋮ An efficient inexact Newton-CG algorithm for the smallest enclosing ball problem of large dimensions ⋮ A branch-and-bound method for the minimum \(k\)-enclosing ball problem ⋮ A new algorithm for the minimax location problem with the closest distance ⋮ Counting unique-sink orientations ⋮ Random sampling with removal ⋮ Combinatorial generalizations of Jung's theorem ⋮ Unique sink orientations of grids ⋮ Algorithms for determining relative position between spheroids and hyperboloids with one sheet ⋮ On a minimum enclosing ball of a collection of linear subspaces ⋮ Covering convex polygons by two congruent disks ⋮ A dual simplex-type algorithm for the smallest enclosing ball of balls ⋮ Solving \(k\)-center problems involving sets based on optimization techniques ⋮ Miniball ⋮ APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING ⋮ Covering convex polygons by two congruent disks

Uses Software

• CGAL
• gmp
• LEDA

Cites Work

• On the ball spanned by balls
• Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\)
• Solution methodologies for the smallest enclosing circle problem
• A subexponential bound for linear programming
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Approximate clustering via core-sets
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Las Vegas algorithms for linear and integer programming when the dimension is small
• A Subexponential Algorithm for Abstract Optimization Problems
• Geometry. I, II. Transl. from the French by M. Cole and S. Levy