# Approximation Algorithms for Smallest Intersecting Balls

arXiv: https://arxiv.org/abs/2406.11369 · HTML: https://mlsanity.com/paper/2406.11369/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2024.

## Built on by (most cited first, 1 of 1)

- [Optimistic Online Learning in Symmetric Cone Games](https://mlsanity.com/paper/2504.03592/) (2025)

## Abstract (arXiv)

We study a general smallest intersecting ball problem and its soft-margin variant in high-dimensional Euclidean spaces for input objects that are compact and convex. These two problems link and unify a series of fundamental problems in computational geometry and machine learning, including smallest enclosing ball, polytope distance, intersection radius, ℓ1-loss support vector machine, ℓ1-loss support vector data description, and so on. Leveraging our novel framework for solving zero-sum games over symmetric cones, we propose general approximation algorithms for the two problems, where implementation details are presented for specific inputs of convex polytopes, reduced polytopes, axis-aligned bounding boxes, balls, and ellipsoids. For most of these inputs, our algorithms are the first results in high-dimensional spaces, and also the first approximation methods. Experimental results show that our algorithms can solve large-scale input instances efficiently.