Efficient algorithms for geometric optimization

We review the recent progress in the design of efficient algorithms for var ious problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternat ives to parametric searching, prune-and-search techniques for linear progra mming and related problems, and LP-type problems and their efficient soluti on. We then describe a wide range of applications of these and other techni ques to numerous problems in geometric optimization, including facility loc ation, proximity problems, statistical estimators and metrology, placement and intersection of polygons and polyhedra, and ray shooting and other quer y-type problems.