An Efficient Vertex Retrieval Algorithm for Ball Polyhedra

Abstract

We consider the intersection $\mathcal{Q}$ of $m$ equal-radius balls in ${\mathbb{R}}^n$ whose centers lie on a common sphere centered at the origin, with the origin contained in the convex hull of the centers. Assuming $\mathcal{Q}$ possesses a unique vertex $x^{\star }$ lying on the hyperplane $1_{n\times 1}^T\cdot x=0$, under a combinatorial-stability assumption, we give a polynomial-time algorithm that recovers $x^{\star }$. The algorithm constructs a one-parameter family of auxiliary polytopes (max-indicator polytopes) whose vertices move radially under a controlled translation of a quadratic center. The distinguished vertex remains fixed, while all others travel along fixed rays. By comparing a pair of symmetrically perturbed polytopes with the unperturbed one and solving a linear number of linear programs, the algorithm isolates $x^{\star }$.