Optimization algorithms for faster computational geometry

DOI10.4230/LIPICS.ICALP.2016.53zbMATH Open1388.68278arXiv1412.1001MaRDI QIDQ4598192FDOQ4598192

Authors: Zeyuan Allen Zhu, Zhenyu Liao, Yang Yuan 

Publication date: 19 December 2017

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 $ildeO(mdalph{a}^3/varepsilo{n}^3)$ to $ildeO(md+msqrtdalpha/varepsilon)$, a speed-up up to $ildeO(sqrtdalph{a}^2/varepsilo{n}^2)$, and MinEB from $ildeO(nd/sqrtvarepsilon)$ to $ildeO(nd+nsqrtd/sqrtvarepsilon)$, a speed-up up to $ildeO(sqrtd)$. 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.

Full work available at URL: https://arxiv.org/abs/1412.1001

Recommendations

• New approximation algorithms for minimum enclosing convex shapes
• Algorithms - ESA 2003
• Geometric median in nearly linear time
• Two Algorithms for the Minimum Enclosing Ball Problem
• Optimization approach for solving some geometry problems

zbMATH Keywords

approximation algorithmsminimum enclosing ballsmaximum inscribed balls

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (3)

• Practical Mixed-Integer Optimization for Geometry Processing
• SVM via saddle point optimization: new bounds and distributed algorithms
• Katyusha: the first direct acceleration of stochastic gradient methods

This page was built for publication: Optimization algorithms for faster computational geometry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598192)