Access Restriction

Author Agarwal, Pankaj K. ♦ Sharir, Micha
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Clustering ♦ Collision detection ♦ Linear programming ♦ Matrix searching ♦ Parametric searching ♦ Proximity problems ♦ Prune-and-search ♦ Randomized algorithms
Abstract 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.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1998-12-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 30
Issue Number 4
Page Count 47
Starting Page 412
Ending Page 458

Open content in new tab

   Open content in new tab
Source: ACM Digital Library