Approximation Algorithms for Smallest Intersecting Balls
<|reference_start|>Approximation Algorithms for Smallest Intersecting Balls: We study a general smallest intersecting ball problem and its soft-margin variant in high-dimensional Euclidean spaces, which only require the input objects to be 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, $\ell_1$-loss support vector machine, $\ell_1$-loss support vector data description, and so on. Two general approximation algorithms are presented respectively, and implementation details are given 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. To achieve this, we develop a novel framework for approximating zero-sum games in Euclidean Jordan algebra systems, which may be useful in its own right.<|reference_end|>
@article{zheng2024approximation,
    title={Approximation Algorithms for Smallest Intersecting Balls},
    author={Jiaqi Zheng, Tiow-Seng Tan},
    journal={arXiv preprint arXiv:2406.11369},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.11369},
    primaryClass={cs.CG cs.DS}
}