AllenZhu, Zeyuan ;
Liao, Zhenyu ;
Yuan, Yang
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 ddimensional space. We improve the running time of iterative algorithms on
MaxIB from ~O(m*d*alpha^3/epsilon^3) to ~O(m*d + m*sqrt(d)*alpha/epsilon), a speedup up to ~O(sqrt(d)*alpha^2/epsilon^2), and
MinEB from ~O(n*d/sqrt(epsilon)) to ~O(n*d + n*sqrt(d)/sqrt(epsilon)), a speedup up to ~O(sqrt(d)).
Our improvements are based on a novel saddlepoint optimization framework. We propose a new algorithm L1L2SPSolver for solving a class of regularized saddlepoint 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.
BibTeX  Entry
@InProceedings{allenzhu_et_al:LIPIcs:2016:6332,
author = {Zeyuan AllenZhu and Zhenyu Liao and Yang Yuan},
title = {{Optimization Algorithms for Faster Computational Geometry}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {53:153:6},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6332},
URN = {urn:nbn:de:0030drops63325},
doi = {10.4230/LIPIcs.ICALP.2016.53},
annote = {Keywords: maximum inscribed balls, minimum enclosing balls, approximation algorithms}
}
23.08.2016
Keywords: 

maximum inscribed balls, minimum enclosing balls, approximation algorithms 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 