Efficient algorithms for geometric optimization

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternatives to parametric searching, p

E cient Algorithms for Geometric Optimization yPankaj K. Agarwal z April 1, 1998AbstractWe review the recent progress in the design of e cient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternatives to parametric searching, prune-and-search techniques for linear programming and related problems, and LP-type problems and their e cient solution. We then describe a wide range of applications of these and other techniques to numerous problems in geometric optimization, including facility location, proximity problems, statistical estimators and metrology, placement and intersection of polygons and polyhedra, and ray shooting and other query-type problems.

Micha Sharir x

Both authors are supported by a grant from the U.S.-Israeli Binational Science Foundation. Pankaj Agarwal has also been supported by National Science Foundation Grant CCR-93{01259, by an Army Research O ce MURI grant DAAH04-96-1-0013, by a Sloan fellowship, and by an NYI award and matching funds from Xerox Corp. Micha Sharir has also been supported by NSF Grants CCR-94-24398 and CCR-9311127, by a Max-Planck Research Award, and by a grant from the G.I.F., the German-Israeli Foundation for Scienti c Research and Development. y A preliminary version of this paper appeared as: P. K. Agarwal and M. Sharir, Algorithmic techniques for geometric optimization, in Computer Science Today: Recent Trends and Developments, Lecture Notes in Computer Science, vol. 1000 (J. van Leeuwen, ed.), 1995, pp. 234{253. z Department of Computer Science, Box 90129, Duke University, Durham, NC 27708-0129, USA. x School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, ISRAEL; and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA.

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternatives to parametric searching, p

Introduction

1

1 IntroductionCombinatorial optimization deals with problems of maximizing or minimizing a function of one or more variables subject to a large number of inequality (and equality) constraints. Many problems can be formulated as combinatorial optimization problems, which has made this a very active area of research during the past half century. In many applications, the underlying optimization problem involves a constant number of variables and a large number of constraints that are are induced by a given collection of geometric objects; we refer to such problems as geometric optimization problems. In such cases one expects that faster and simpler algorithms can be developed by exploiting the geometric nature of the problem. Much work has been done on geometric optimization problems during the last twenty years. Many new elegant and sophisticated techniques have been developed and successfully applied to a wide range of geometric optimization problems. The aim of this paper is to survey the main techniques and applications of this kind. This survey consist of two parts. The rst part describes s

everal general techniques that have led to e cient algorithms for a variety of geometric optimization problems, the most notable of which is linear programming. The second part lists many geometric applications of these techniques and discusses some of them in more detail. The rst technique that we present is called parametric searching. Although restricted versions of parametric searching already existed earlier (see e.g. 112]), the full-scale technique was presented by Megiddo in the late 1970s and early 1980s 209, 210]. The technique was originally motivated by so-called parametric optimization problems in combinatorial optimization, and did not receive much attention by the computational geometry community until the late 1980s. In the last seven years, though, it has become one of the major techniques for solving geometric optimization problems e ciently. We outline the technique in detail in Section 2, rst exemplifying it on the slope-selection problem 77], and then presenting various extensions of the technique. Despite its power and versatility, parametric searching has certain drawbacks, which we discuss next. Consequently, there have been several recent attempts to replace parametric searching by alternative techniques, including randomization 15, 54, 73, 199], expander graphs 30, 176, 179, 178], geometric cuttings 18, 49], and matrix searching 124, 125, 126, 127, 131]. We present these alternative techniques in Section 3. Almost concurrently with the development of the parametric searching technique, Megiddo devised another ingenious technique for solving linear programming and several related optimization problems 211, 213]. This technique, now known as decimation or prune-andsearch, was later re ned and extended by Dyer 99], Clarkson 68], and others. The technique can be viewed as an optimized version of parametric searching, in which certain special properties of the problem allows one to improve further the e ciency of the algorithm. For example, this technique yields linear-time deterministic algorithms for linear programmingGeometric Optimization April 1, 1998

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternatives to parametric searching, p

Introduction

2

and for several rel …… 此处隐藏：50384字，全部文档内容请下载后查看。喜欢就下载吧 ……