Linear Optimization Queries

Let Γ₀ be a set of n halfspaces in E^d (where the dimension d is fixed) and let m be a parameter, n ≤ m ≤ n^d/2. We show that Γ₀ can be preprocessed in time and space O(m^1+δ) (for any fixed δ > 0) so that given a vector c E^d and another set Γ_q of additional halfspaces, the function c · x can be optimized over the intersection of the halfspaces of Γ₀ Γ_q in time O((n/m^1/d/2 + |Γ_q|)log^4d+3n). The algorithm uses a multidimensional version of Megiddo′s parametric search technique and recent results on halfspace range reporting. Applications include an improved algorithm for computing the extreme points of an n-point set P in E^d, improved output-sensitive computation of convex hulls and Voronoi diagrams, and a Monte-Carlo algorithm for estimating the volume of a convex polyhedron given by the set of its vertices (in a fixed dimension).