Efficient Algorithms for Geometric OptimizationPANKAJ K. AGARWALDuke UniversityANDMICHA SHARIRTel Aviv UniversityWe review the recent progress in the design of efficient algorithms for variousproblems in geometric optimization. We present several techniques used to attackthese problems, such as parametric searching, geometric alternatives to parametricsearching, prune-and-search techniques for linear programming and relatedproblems, and LP-type problems and their efficient solution. We then describe awide range of applications of these and other techniques to numerous problems ingeometric optimization, including facility location, proximity problems, statisticalestimators and metrology, placement and intersection of polygons and polyhedra,and ray shooting and other query-type problems.Categories and Subject Descriptors: A.1 [General]: Introductory and Survey; F.2.2[Theory of Computation]: Analysis of Algorithms and Problems—Geometricalproblems and computations; I.1.2 [Computing Methodologies]:Algorithms—Analysis of algorithmsGeneral Terms: Algorithms, DesignAdditional Key Words and Phrases: Clustering, collision detection, linearprogramming, matrix searching, parametric searching, proximity problems, prune-and-search, randomized algorithms1. INTRODUCTIONCombinatorial optimization typicallydeals with problems of maximizing orminimizing a function of one or morevariables subject to a large number ofinequality (and equality) constraints.Many problems can be formulated ascombinatorial optimization problems,which has made this a very active areaBoth authors are supported by a grant from the U.S.-Israeli Binational Science Foundation. P. K.Agarwal has also been supported by National Science Foundation Grant CCR-93-01259, Army ResearchOffice MURI grant DAAH04-96-1-0013, a Sloan fellowship, and an NYI award and matching funds fromXerox Corp. M. Sharir has also been supported by NSF Grants CCR-94-24398 and CCR-93-11127, aMax-Planck Research Award, and a grant from the G.I.F., the German-Israeli Foundation for ScientificResearch and Development. A preliminary version of this article appeared as: P. K. Agarwal and M.Sharir, Algorithmic techniques for geometric optimization, in Computer Science Today: Recent Trendsand Developments, LNCS 1000, J. van Leeuwen, Ed., 1995, pp. 234–253.Authors’ addresses: P. K. Agarwal, Center for Geometric Computing, Department of Computer Science,Box 90129, Duke University, Durham, NC 27708-0129; M. Sharir, School of Mathematical Sciences, TelAviv University, Tel Aviv 69978, Israel, and Courant Institute of Mathematical Sciences, New YorkUniversity, New York, NY 10012.Permission to make digital/hard copy of part or all of this work for personal or classroom use is grantedwithout fee provided that the copies are not made or distributed for profit or commercial advantage, thecopyright notice, the title of the publication, and its date appear, and notice is given that copying is bypermission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute tolists, requires prior specific permission and/or a fee.© 1999 ACM 0360-0300/99/1200–0412 $5.00ACM Computing Surveys, Vol. 30, No. 4, December 1998of research during the past half century.In many applications, the underlyingoptimization problem involves a con-stant number of variables and a largenumber of constraints that are inducedby a given collection of geometric ob-jects; we refer to such problems as geo-metric-optimization problems. In suchcases one expects that faster and sim-pler algorithms can be developed by ex-ploiting the geometric nature of theproblem. Much work has been done ongeometric-optimization problems duringthe last 20 years, and many new elegantand sophisticated techniques have beendeveloped and successfully applied tothem. The aim of this article is to sur-vey the main techniques and applica-tions of this kind.The first part of this survey describesseveral general techniques that haveled to efficient algorithms for a varietyof geometric-optimization problems, themost notable of which is linear pro-gramming. The second part lists manygeometric applications of these tech-niques and discusses some of them inmore detail.The first technique that we present iscalled parametric searching. Althoughrestricted versions of parametricsearching existed earlier (see, e.g., Eis-ner and Severance [1976]), the full-scaletechnique was presented by Megiddo[1979, 1983a] in the late 1970s andearly 1980s. The technique was origi-nally motivated by so-called parametric-optimization problems in combinatorialoptimization, and did not receive muchattention by the computational geome-try community until the late 1980s. Inthe last decade, though, it has becomeone of the major techniques for solvinggeometric-optimization problems effi-ciently. We outline the technique in de-tail in Section 2, first exemplifying it onthe slope-selection problem [Cole et al.1989], and then presenting various ex-tensions of the technique.Despite its power and versatility,parametric searching has certain draw-backs, which we discuss next. Conse-quently, there have been several recentattempts to replace parametric search-ing by alternative techniques, includingrandomization,1expander graphs,2geo-metric cuttings [Agarwal et al. 1993c;Bro¨nnimann and Chazelle 1994], andmatrix searching.3We present these al-ternative techniques in Section 3.Almost concurrently with the develop-ment of the parametric-searching tech-nique, Megiddo [1983b, 1984] devisedanother ingenious technique for solvinglinear programming and several relatedoptimization problems. This technique,now known as decimation or prune-and-search, was later refined and extendedby Dyer [1984], Clarkson [1986], andothers. The technique can be viewed asan optimized version of parametricsearching, in which certain specialproperties of the problem allow one toimprove further the efficiency of thealgorithm. For example, this techniqueyields linear-time deterministic algo-rithms for linear programming and forseveral related problems, including thesmallest-enclosing-ball problem, whenthe dimension is fixed. (However, thedependence of the running time of thesealgorithms on the dimension is at bestexponential.) We illustrate the tech-nique in Section 4 by applying it tolinear programming.In the past decade, randomized algo-rithms have been developed for a vari-ety of problems in computational geom-etry and in other fields; see, forexample, the books by