Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries

Bahman Kalantari, Yikai Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish (US)
Article number23
JournalACM Transactions on Mathematical Software
Volume48
Issue number2
DOIs
StatePublished - Jun 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Applied Mathematics

Keywords

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

Fingerprint

Dive into the research topics of 'Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries'. Together they form a unique fingerprint.

Cite this