FAST AND OPTIMAL PARALLEL MULTIDIMENSIONAL SEARCHIN PRAMS WITH APPLICATIONS TO LINEAR PROGRAMMINGAND RELATED PROBLEMS∗MARTIN E. DYER†AND SANDEEP SEN‡SIAM J. COMPUT.c2000 Society for Industrial and Applied MathematicsVol. 30, No. 5, pp. 1443–1461Abstract. We describe a deterministic parallel algorithm for linear programming in fixed di-mension d that takes poly(log log n) time in the common concurrent read concurrent write (CRCW)PRAM model and does optimal O(n) work. In the exclusive read exclusive write (EREW) model,the algorithm runs in O(log n · log logd−1n) time. Our algorithm is based on multidimensional searchand effective use of approximation algorithms to speed up the basic search in the CRCW model. Ourmethod also yields very fast poly(log log n) algorithms for smallest enclosing sphere and approximateham-sandwich cuts and an O(log n) time work-optimal algorithm for exact ham-sandwich cuts ofseparable point sets. For these problems, in particular for fixed-dimensional linear programming,o(log n) time efficient deterministic PRAM algorithms were not known until very recently.Key words. parallel algorithms, computational geometry, linear programmingAMS subject classifications. 68W10, 68W40, 65D18, 90C05PII. S00975397973257271. Introduction. We consider the standard linear programming problem: givena set H of n half-spaces in Rdand a vector y, find a point x ∈H that minimizesy · x. We restrict ourselves to the case where n is much larger than d, and we fo-cus attention on parallel algorithms that achieve good performance with respect ton. Since the general problem is known to be P-complete [12], the restricted versionassumes more relevance. For the most part we will regard d as a constant. However,since the running time of our algorithm grows rapidly with d, we will attempt toexamine the exact nature of this dependence. Megiddo [32] described a linear-timealgorithm for linear programming in fixed dimension d (hereafter referred to as LPd),using an elegant multidimensional search technique. The same search technique, alsoknown as prune-and-search, yielded optimal algorithms for other optimization prob-lems (see Megiddo [31] and Dyer [13, 14]). Following Megiddo’s linear-time algorithm,there have been significant improvements in the constant factor (which was doublyexponential in d) due to Dyer [14] and Clarkson [4]. Further progress was made,using random sampling, by Clarkson [5]. This algorithm was later derandomized byChazelle and Matouˇsek [9]. With more careful analysis and some additional ideas,Matouˇsek, Sharir, and Welzl [30] improved the algorithm further, achieving an ex-pected running time of O(d2· n + eO(√d log d)), a “subexponential” dependence on d.Independently, Kalai [26] discovered an algorithm with matching performance, andthese are presently the fastest known algorithms.In the context of parallel algorithms for LPd, there have been a number of re-sults in the direction of finding a fast analogue of Megiddo’s linear-time sequential∗Received by the editors August 12, 1997; accepted for publication (in revised form) June 12, 2000;published electronically November 8, 2000. Preliminary versions of the main results of this paperappeared in [Proceedings of the 11th ACM Symposium on Computational Geometry, Vancouver,Canada, 1995, pp. 345–349.] and [Proceedings of the ACM Symposium on Parallel Algorithms andArchitectures, Padua, Italy, 1996, pp. 251–260.].http://www.siam.org/journals/sicomp/30-5/32572.html†School of Computer Studies, University of Leeds, Leeds LS2 9JT, UK ([email protected]).‡Department of Computer Science and Engineering, Indian Institute of Technology, New Delhi110016, India ([email protected]).14431444 MARTIN E. DYER AND SANDEEP SENmethod [1, 2, 11, 34]. A straightforward parallelization of Megiddo’s method yields anO(logdn) time n-processor exculsive read exclusive write (EREW) PRAM algorithm.(We write logkn for (log n)k, and, similarly, log logkn for (log log n)k.) However, thisis far from the best that can be achieved. Alon and Megiddo [2] obtained an opti-mal parallel algorithm that runs in constant time (i.e., time depending only on d)onan n-processor randomized concurrent read concurrent write (CRCW) PRAM model.They used a variant of Clarkson’s algorithm [5], which has smaller constants (in termsof d) than Megiddo’s. More recently, Ajtai and Megiddo [1] developed a deterministicO(log logdn) algorithm in an n processor model which allows O(log log n) time selec-tion. Since there is an Ω(log n/ log log n) bound for exact selection [3], their model isconsiderably more powerful than the CRCW model, and partly nonuniform. It mayalso be noted that the work bound in the algorithm of Ajtai and Megiddo is superlin-ear, since they use a linear number of processors. Thus an o(log n) time optimal deter-ministic algorithm for LPd had hitherto proved elusive. Very recently, Goodrich [19](see also Goodrich and Ramos [20]) independently obtained a poly(log log n) timeCRCW algorithm with optimal speed-up using fast parallel derandomization tech-niques. His approach is different from ours, being directly based on parallel deran-domization techniques. His underlying randomized algorithm is similar to that ofDyer and Frieze [16]. This is derandomized using fast deterministic constructions ofε-approximations in Rd. Here, we generalize the basic multidimensional search algo-rithm of Megiddo. Instead of pruning a constant fraction of the constraints in eachround, we increase the rate of pruning as a function of processor advantage. Theprocessor advantage is proportional to the ratio of the number of processors to thenumber of constraints, which increases monotonically during the course of the search.This allows us to improve the Ω(log n) phases seemingly required by Megiddo’s ap-proach, and leads to a fast EREW algorithm. However, it does not directly yield apoly(log log n) CRCW algorithm for the following reason. All known versions of multi-dimensional search algorithms rely on exact selection procedures, either deterministicor randomized. We make use of the observation that exact selection may be substi-tuted by approximate splitting (defined formally in section 3) without significantlyaffecting the asymptotic convergence rate of the procedure. This is crucial in order tosurmount the Ω(log n/ log log n) barrier for exact parallel selection: an impossibilityin Ajtai and Megiddo’ s