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 tildeO(m d α3 / varepsilon3) to tildeO(md + m √d α / varepsilon), a speed-up up to tildeO(√d α2 / varepsilon2), and MinEB from tildeO(n d / √varepsilon) to tildeO(nd + n √d / √varepsilon), a speed-up up to tildeO(√d). Our improvements are based on a novel saddle-point optimization framework. We propose a new algorithm mathttL1L2SPSolver 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.