Efficient Algorithms for Geometric Optimization

Published

Journal Article

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, prune-and-search techniques for linear programming and related problems, and LP-type problems and their efficient 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. Categories and Subject Descriptors: A.1 [General]: Introductory and Survey; F.2.2 [Theory of Computation]: Analysis of Algorithms and Problems—Geometrical problems and computations; I.1.2 [Computing Methodologies]: Algorithms—Analysis of algorithms. © 1998, ACM. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sharir, M

Published Date

  • December 1, 1998

Published In

Volume / Issue

  • 30 / 4

Start / End Page

  • 412 - 458

Electronic International Standard Serial Number (EISSN)

  • 1557-7341

International Standard Serial Number (ISSN)

  • 0360-0300

Digital Object Identifier (DOI)

  • 10.1145/299917.299918

Citation Source

  • Scopus