Backwards analysis of randomized geometric algorithms

From MaRDI portal





A survey paper, gives an excellent introduction to randomized algorithms in computational geometry and to a simple method of estimating their expected running time. The method (backwards analysis) is explained on several examples: computing the Delaunay triangulation of a convex polygon in the plane, computing the convex hull of a point set in a fixed dimension, solving a linear programming problem in a fixed dimension, computing all intersections of a given set of segments in the plane and computing the smallest circle enclosing a given planar point set. These are fundamental computational geometry problems, and the presented algorithms are simple and mostly they have asymptotically optimal expected running time. The subject is treated in greater detail in \textit{K. Mulmuley} [Computational Geometry: An Introduction Through Randomized Algorithms (Prentice Hall, New York, 1993)]. Some of the open problems in the paper have been solved by now; see e.g. \textit{B. Chazelle}, \textit{H. Edelsbrunner}, \textit{L. Guibas}, \textit{M. Sharir} and \textit{J. Snoeyink} [SIAM J. Comput. 22, No. 6, 1286-1302 (1993; Zbl 0799.68182)]. For the entire collection see [Zbl 0773.00009].




Cited in
(26)








This page was built for publication: Backwards analysis of randomized geometric algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3138743)