2026-08-10T11:23:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6332 2024-03-06T10:37:44Z ddc:004 open_access

Optimization Algorithms for Faster Computational Geometry Allen-Zhu, Zeyuan Liao, Zhenyu Yuan, Yang maximum inscribed balls minimum enclosing balls approximation algorithms 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*alpha^3/epsilon^3) to ~O(m*d + m*sqrt(d)*alpha/epsilon), a speed-up 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 speed-up up to ~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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeyuan Allen-Zhu and Zhenyu Liao and Yang Yuan 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.53 urn:nbn:de:0030-drops-63325 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.53 eng https://creativecommons.org/licenses/by/3.0/legalcode