2014/12/02 by Allen-Zhu, Zeyuan, Liao, Zhenyu, Yuan, Yang · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1412.1001
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 O(m d α3 / ε3) to O(md + m √(d) α/ ε), a speed-up up to O(√(d) α2 / ε2), and MinEB from O(n d / √(ε)) to O(nd + n √(d) / √(ε)), a speed-up up to O(√(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.