# Optimization Algorithms for Faster Computational Geometry

arXiv: https://arxiv.org/abs/1412.1001 · HTML: https://mlsanity.com/paper/1412.1001/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2014.

## Built on by (most cited first, 3 of 3)

- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Off-policy Reinforcement Learning with Optimistic Exploration and Distribution Correction](https://mlsanity.com/paper/2110.12081/) (2021)
- [Sublinear Time Algorithms for Several Geometric Optimization (With Outliers) Problems In Machine Learning](https://mlsanity.com/paper/2301.02870/) (2023)

## Abstract (arXiv)

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.