Smallest Intersecting and Enclosing Balls

Jiaqi Zheng, Tiow-Seng Tan · 2025

Read Smallest Intersecting and Enclosing Balls by Jiaqi Zheng, Tiow-Seng Tan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18178.txt.

Description

Jiaqi Zheng and Tiow-Seng Tan unified two classic ball problems in a 2025 geometry paper. Given a set of compact convex objects, the smallest intersecting ball is the tiniest ball touching them all, while the smallest enclosing ball is the tiniest ball containing them all. Versions of these problems recur across computational geometry and machine learning, from facility placement to classifier margins.

Zheng and Tan show both problems can be written as zero-sum games, where two players' opposing goals encode the geometry. For the intersecting version they give an approximation algorithm, the first results of its kind in high dimensions for inputs like polytopes, balls, and ellipsoids. The game view may unlock algorithms for related covering problems.

Catalog record

CREATORJiaqi Zheng, Tiow-Seng Tan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE10 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-18178

Browse the full library · About the Tower of Babel