Abstract: We study two fundamental problems in computational geometry: finding the maximum inscribed ball (MaxIB) inside a bounded polyhedron defined by $m$ hyperplanes, and the minimum enclosing ball (MinEB) of a set of $n$ points, both in $d$-dimensional space. We improve the running time of iterative algorithms on MaxIB from $\tilde{O}(m d \alpha^3 / \varepsilon^3)$ to $\tilde{O}(md + m \sqrt{d} \alpha / \varepsilon)$, a speed-up up to $\tilde{O}(\sqrt{d} \alpha^2 / \varepsilon^2)$, and MinEB from $\tilde{O}(n d / \sqrt{\varepsilon})$ to $\tilde{O}(nd + n \sqrt{d} / \sqrt{\varepsilon})$, a speed-up up to $\tilde{O}(\sqrt{d})$. Our improvements are based on a novel saddle-point optimization framework. We propose a new algorithm $\mathtt{L1L2SPSolver}$ for solving a class of regularized saddle-point problems, and apply a randomized Hadamard space rotation which is a technique borrowed from compressive sensing. Interestingly, the motivation of using Hadamard rotation solely comes from our optimization view but not the original geometry problem: indeed, it is not immediately clear why MaxIB or MinEB, as a geometric problem, should be easier to solve if we rotate the space by a unitary matrix. We hope that our optimization perspective sheds lights on solving other geometric problems as well.
Introduction
Computational geometry often grapples with problems that become increasingly difficult as dimensionality increases. Two such classic problems are finding the Maximum Inscribed Ball (MaxIB) and the Minimum Enclosing Ball (MinEB). While these are well-studied, existing iterative algorithms often struggle with high dimensions ($d$) or the need for high precision (small error $\epsilon$). This research bridges the gap between geometry and modern optimization by reframing these challenges as regularized saddle-point problems, achieving significant theoretical speedups.
The Geometric Problem
The research focuses on two primary geometric tasks in $d$-dimensional space:
- Maximum Inscribed Ball (MaxIB): Identifying the largest ball that can be contained within a polyhedron defined by $m$ hyperplanes. This is a core problem in operations research and shape analysis.
- Minimum Enclosing Ball (MinEB): Identifying the smallest ball that contains a given set of $n$ points. This has wide applications in data clustering and facility location.
For MaxIB, previous state-of-the-art methods suffered from a cubic dependence on the "skinny-ness" or aspect ratio ($\alpha$) of the polyhedron and the inverse error ($1/\epsilon$). The goal of this work is to reduce this complexity to nearly linear time relative to the input size.
A Novel Optimization Framework
The core innovation lies in translating these geometric problems into an $\ell_1-\ell_2$ regularized saddle-point program. This shift allows the application of advanced optimization techniques:
The L1L2SPSolver
The authors introduce a new stochastic, coordinate-based first-order algorithm. Unlike traditional solvers that update all variables simultaneously, this algorithm randomly selects coordinates for one set of variables while employing "multiplicative weight updates" for the other. This approach significantly reduces the computational cost per iteration.
Randomized Hadamard Rotation
Borrowing from compressive sensing, the authors apply a randomized rotation to the entire space. While a unitary rotation does not change the geometric properties (the size of the balls remains invariant), it serves a critical purpose in optimization. Coordinate-based solvers typically perform poorly when data is unbalanced—for instance, when one hyperplane is significantly more restrictive than others. The rotation "spreads out" the influence of constraints, uniformizing the data and allowing the coordinate-based solver to converge much faster.
Key Insights and Theoretical Results
The "aha moment" of this research is the realization that MaxIB and MinEB are naturally structured as saddle-point problems where one side is strongly convex (the $\ell_2$ part) and the other is strongly concave (the $\ell_1$ part). By treating rotation as a preprocessing step to uniformize matrix entries, the authors break the cubic barrier for high-precision applications.
The theoretical improvements are substantial:
- MaxIB: Complexity is reduced from $\tilde{O}(md\alpha^3/\epsilon^3)$ to $\tilde{O}(md + m\sqrt{d}\alpha/\epsilon)$, representing a speedup of up to $\sqrt{d}\alpha^2/\epsilon^2$.
- MinEB: Complexity is reduced from $\tilde{O}(nd/\sqrt{\epsilon})$ to $\tilde{O}(nd + n\sqrt{d}/\sqrt{\epsilon})$, a speedup of up to $\sqrt{d}$.
To put this in perspective, for a 100-dimensional problem with an aspect ratio of 10 and 10% error, this method could theoretically be $10^5$ times faster than previous influential algorithms.
Conclusion and Future Work
This work demonstrates that an optimization perspective can provide powerful new tools for solving classic geometric problems. By leveraging randomized rotations and coordinate-based solvers, the authors achieve nearly linear time complexity for MaxIB and MinEB.
As a theoretical contribution, the paper focuses on mathematical proofs of improved running times rather than empirical benchmarks. Future work remains to evaluate the practical performance of these algorithms on real-world datasets and to address the preprocessing requirements, such as the "warm start" needed for the MaxIB algorithm.
Summary updated