Optimization Algorithms for Faster Computational Geometry

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}(md{\alpha }^3\mathrm{/}{\epsilon }^3)$ to $\tilde{O}(md + m \sqrt{d} \alpha / \varepsilon)$,aspeed-upupto$\tilde{O}(\sqrt{d} \alpha^2 / \varepsilon^2)$, and MinEB from $\tilde{O}(nd\mathrm{/}\sqrt{\epsilon })$ to $\tilde{O}(nd + n \sqrt{d} / \sqrt{\varepsilon})$,aspeed-upupto$\tilde{O}(\sqrt{d})$. Our improvements are based on a novel saddle-point optimization framework. We propose a new algorithm $\mathtt{L}\mathtt{1}\mathtt{L}\mathtt{2}\mathtt{S}\mathtt{P}\mathtt{S}\mathtt{o}\mathtt{l}\mathtt{v}\mathtt{e}\mathtt{r}$ 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.