Optimization Algorithms for Faster Computational Geometry

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}(md{\alpha }^3/{\epsilon }^3)$ to $\tilde{O}(md+m\sqrt{d}\alpha /\epsilon )$, a speed-up up to $\tilde{O}(\sqrt{d}{\alpha }^2/{\epsilon }^2)$, and MinEB from $\tilde{O}(nd/\sqrt{\epsilon })$ to $\tilde{O}(nd+n\sqrt{d}/\sqrt{\epsilon })$, 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 $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.

An abstract of this paper is going to appear in the conference proceedings of ICALP 2016