Approximation Algorithms for Smallest Intersecting Balls
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908379328282624 |
|---|---|
| author | Zheng, Jiaqi Tan, Tiow-Seng |
| author_facet | Zheng, Jiaqi Tan, Tiow-Seng |
| contents | 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, $\ell_1$-loss support vector machine, $\ell_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_11369 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for Smallest Intersecting Balls Zheng, Jiaqi Tan, Tiow-Seng Computational Geometry Data Structures and Algorithms 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, $\ell_1$-loss support vector machine, $\ell_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. |
| title | Approximation Algorithms for Smallest Intersecting Balls |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.11369 |