LINEAR OPTIMIZATION QUERIES

Let Γ0 be a set of n halfspaces in Ed (where the dimension d is fixed) and let m be a parameter, n ≤ m ≤ n⌊d/2⌋. We show that Γ0 can be preprocessed in time and space O(m1+δ) (for any fixed δ > 0) so that given a vector c ∈ Ed and another set Γq of additional halfspaces, the function c · x can be optimized over the intersection of the halfspaces of Γ0 ∪ Γq in time O((n/m1/⌊d/2⌋ + |Γq|)log4d+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 Ed, 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). © 1993 Academic Press, Inc.