Linear optimization queries*AbstractJiii Matou5ektDepartment of Applied Mathematics, Charles LJniversityMalostransk6 n~m. 25, 11800 Praha 1, CzechoslovakiaOtfried Schwarzkopf $Utrecht University, Department of Computer ScienceP.O. Box 80.089, 3508 TB Utrecht, the NetherlandsLet F be a set of n halfspaces in Ed (where the di-mension d ~ 3 is fixed) and c a d-component vector.We denote by LP(I’, c) the linear programming prob-lem of minimizing the function c . x over the intersec-tion of all ha~spaces of I’. We show that r can bepreprocessed in time and space O(ml+j) (for any fixed& >0, m is an adjustable parameter, n < m < nldizj)so that given c c Ed, LP(I’, c) can be solved in ttmeO((m,/~./,J + lrq 1) log2d+1 n). The data structure canbe dynamically maintained under insertions and dele-tions of hyperplanes from 17, in 0(m1+3/n) amortizedi!ime per update operation. We use a multidimensionalversion of Megiddo ’s parametric search technique.In connection with an output-sensitive algorithm ofSeidel, we get that a convex hull of an n-point set inEd (d ~ 4) can be computed in time 0(n2”*+h +h log n), where h is the number of faces of the con-vex hull. We also show that given an n-point set Pin Ed,one can determine the extreme points of P mtime 0(n2-*f6) (for any fixed 6> o).*This extended abstract combines a paper [Mat91d] of the firstauthor with an improvement and simplification achieved by thesecond author in [Sch91].t The research by J. M, was performed while he was visiting atSchool of Mathematics, Georgia Institute of Technology, Atlanta.t 0. S. acknowledges support by the ESPRIT II Basic ResearchAction of the European Community under contract No. 3075(project AI.ICOM). This research was done while he was e~nployedat Freie Universit?4t Berlin. Furthermore, part of this research wasdone while he visited INRIA-Sophia Antipolis.Permission to copy without fee all or part of thismaterial is grantedprovided that the copies are not made or dktributed for directcommercialadvantage, the ACM copyright notice and the title of thepublication and its date appear, and notice is given that copying is bypermission of the Association for Computing Machine~. To copy other-wise, or to republish, requires a fee and/or specific permission.1 Introduction and statement of resultsThis research was originally motivated by the followingproblem: Let P be an n-point set in Ed, where thedimension d is fixed; determine which points of P areextreme (we call a point x E P eztreme if conv(P \{z}) # conv(P)). In dimensions 2 and 3, this problemcan be solved relatively easily in optimal time O(n log n)by computing the convex hull of P (see [PH77]). But ifthe dimension is at least 4, then the complexity of anexplicit description of the convex hull of P may be toolarge, since conv(P) can have up to Q(nLd/2j ) facets.It is not difficult to see that the question “is z ex-treme in P?”can be formulated as a linear program-ming problem with d variables. Megiddo [Meg84] hasshown that a linear program with d variables and nconstraints can be solved in O(n) time. In Megiddo’soriginal solution, the constant of proportionality growsdoubly exponentially with d. Subsequent solutions im-proved this to a single exponential growth ([Dye86],[Cla86]). Also randomized algorithms with linear ex-pected running time are known; the best asymptotic de-pendence on the dimension has been achieved by Clark-son [Cla88a], and a particularly simple algorithm wasgiven by Seidel [Sei90].With linear programming in linear time, the extremepoints can be found in 0(n2) time. Recently Seidel andWelzl [SW90] improved this complexity to 0(n312 log n)in dimension 4 and to 0(n2- cd logO(ll n) in any fixeddimension d ~ 5, where l/cd = 0( [d/2J !2). They use arandomized divide-and conquer to partition the prob-lem into suitable smaller subproblems, which are thensolved by linear programming.Here we improve their result. We describe a way topreprocess a point set P in Ed for fast answering ofseparation queries. Given a query point z E Ed, ouralgorithm either finds a hyperplane h containing z andsuch that all points of P lie in one of the open halfspacesbounded by h, or determines that no such hyperplane8th Annual Computational Geometry, 6/92, Berlin, Germany@1992 ACM 89791-518-6/92/0006/0016 ... . . . . .. $1.5016exists.Theorem1.1 Given an n-point set P in Ed and aparameter m, n < m < nldlz~ , one can preprocessP with space and preprocessing time O(ml+d) for anyjixed 6>0, so that se{;~tion querzes can be answeredin time 0( ~l,~~,zr logn). The data structure canbe maintained in O(mltj/n) amortized time per tn-sert/delete operation.With a small modification of this data structure andwhen the query time for n queries and the preprocessingtime are balanced appropriately, we obtainTheorem 1,2 The extreme potnts of an n-point set inEd can be found in tzme O(nz-%+d) (for any fixedb >o).Our approach can be easily extended to handle lineuroptimization queries. Let r be a set of halfspaces in Edand c a d-component vector. We denote by LP(17, c) thelinear programming problem of minimizing the functionc. z over the intersection of all halfspaces of r. We showthat one can preprocess a given set I’. of halfspaces sothat for a given c, LP (I’., c) can be solved quickly. Wemay even add a set I’~ of additional constraints (half-spaces) to the query and solve LP(I’OU rq, c) quickly.Results of this type for dimensions 2 and 3 were givenby Guibas, Stolfi and Clarkson [GSC87]; they show thatif the query consists of c only, the solution can be foundin O(log n) time, where n = 11’01, with O(n log n) timepreprocessing and O(n) storage.For a dynamic version of the problem (when up-dates on I’. are allowed) and for dimension 3, Epp-stein [Epp91] gave a data structure for the special casewhen the sequence of insertionsldeletions is known inadvance. For d < 4 and assuming a random sequenceof updates, Mulmuley [Mu191] gave an algorithm whichhas a polylogarithmic query time with high probability,and with expected amortized update costs O(log n) ford = 3, resp. 0(nlog2n) for d = 4.We have the following quantitative results:Theorem 1.3 One can preprocess a set I’. of n half-spaces in Edin O(ml+J) (determanistac) tame andspace, for a parameter m,n~ m < n,ld!/2Jand some fixed 6 > 0, so that given a– query d;component vector c and a set rq of additional italf-spaces, the problem LP(I’OU rq, c) can be solved in tzmeO((m,,~,,,J + Irgl) logzd+l n). The data