Linear programming queries revisited
Edgar A. Ramos · 2000
IntroductionWe describe an approach for answering linear programming queries with respect to a set of n linear constraints in l~ d, for a fixed dimension d.Solutions to this problem had been given before by Ma-tou~ek (1993) using a multidimesional version of parametric search and by Chan (1996) using randomization and C!arkson's approach to linear programming.These previous approaches use data structures for halfspace-range emptiness queries and reporting queries, respectively.Our approach is a generalization of Chan's: it also uses halfspace-range reporting data structures, Clarkson's approach to linear programming, and avoids parametric search; unlike Chan's appraoch, it gives deterministic solutions without considerable additional preprocessing overhead.The new solution is as good or improves the previous solutions in all the range of storage space: with O(n ld/2j log °( 1) n) storage space, it achieves query time O(log c log d n), where c is a small constant independent from d, in comparison to O(log d+l n) for Matougek's data structure and O(n c log d) for Chan's; with O(n) storage space, it achieves, as Chan's data structure, query time O(nl-1/[d/2J20(l°g* n)) after O(nl~ -~) preprocessing, but without using randomization.Linear programming has received a great amount of attention in computational geometry because of its importance in applications and its relative simplicity.An important early discovery was that it can be performed in time linear in the number of constraints [16].Several alternative algorithms have been presented subsequently, both deterministic [3] and randomized [5,17,15].We consider the problem of linear programming queries: Given a set H of n linear constraints in ]~d (halfspaces), with the dimension d fixed, construct a data structure so that given a query linear function w (vector), the minimum of w restricted to N H = DhEH h can be determined efficiently.This was first solved "almost completely" by Matou~ek [13] using a multidimensional version of parametric search together with data structures for halfspace-range emptiness queries.Later, Chan [2] presented an alternative approach which through randomization reduced the problem to halfspace-range reporting queries.Chan's approach is conceptually simpler and achieves better query times in the case of small storage space; however, comparatively, it performs poorly when the storage space is large.An interesting and useful feature of Chan's approach is that it uses the half-space range reporting data structure as a black-box.