Backwards Analysis of Randomized Geometric Algorithms

TitleBackwards Analysis of Randomized Geometric Algorithms
Publication TypeTechnical Report
Year of Publication1992
AuthorsSeidel, R..
Other Numbers719

The theme of this paper is a rather simple method that has proved very potent in the analysis of the expected performance of various randomized algorithms and data structures in computational geometry. The method can be described as ``analyze a randomized algorithm as if it were running backwards in time, from output to input.'' We apply this type of analysis to a variety of algorithms, old and new, and obtain solutions with optimal or near optimal expected performance for a plethora of problems in computational geometry, such as computing Delaunay triangulations of convex polygons, computing convex hulls of point sets in the plane or in higher dimensions, sorting, intersecting line segments, linear programming with a fixed number of variables, and others.

Bibliographic Notes

ICSI Technical Report TR-92-014

Abbreviated Authors

R. Seidel

ICSI Publication Type

Technical Report