## Abstract

The Convex Hull Membership (CHM) tests whether , where p and the n points of S lie in . CHM finds applications in Linear Programming, Computational Geometry, and Machine Learning. The Triangle Algorithm (TA), previously developed, in iterations computes , either an -approximate solution, or a witness certifying . We first prove the equivalence of exact and approximate versions of CHM and Spherical-CHM, where and for each v in S. If for some every non-witness with admits satisfying , we prove the number of iterations improves to and always holds. Equivalence of CHM and Spherical-CHM implies Minimum Enclosing Ball (MEB) algorithms can be modified to solve CHM. However, we prove -approximation in MEB is -approximation in Spherical-CHM. Thus, even iteration MEB algorithms are not superior to Spherical-TA. Similar weakness is proved for MEB core sets. Spherical-TA also results a variant of the All Vertex Triangle Algorithm (AVTA) for computing all vertices of . Substantial computations on distinct problems demonstrate that TA and Spherical-TA generally achieve superior efficiency over algorithms such as Frank-Wolfe, MEB, and LP-Solver.

Original language | English (US) |
---|---|

Article number | 23 |

Journal | ACM Transactions on Mathematical Software |

Volume | 48 |

Issue number | 2 |

DOIs | |

State | Published - Jun 2022 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Software
- Applied Mathematics

## Keywords

- Convex Hull Membership
- data reduction
- Machine Learning
- minimum enclosing ball
- Triangle Algorithm