Backwards analysis of randomized geometric algorithms
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].
- An introduction to randomization in computational geometry
- Randomized geometric algorithms and pseudorandom generators
- scientific article; zbMATH DE number 410386
- Derandomization in Computational Geometry
- scientific article; zbMATH DE number 1424301
- scientific article; zbMATH DE number 1256644
- scientific article; zbMATH DE number 1182927
- Applications of random sampling to on-line algorithms in computational geometry
- An optimal convex hull algorithm in any fixed dimension
- Towards dynamic randomized algorithms in computational geometry
- Comparison of simple diversity mechanisms on plateau functions
- Small-dimensional linear programming and convex hulls made easy
- Stable minimum space partitioning in linear time
- An applied point pattern matching problem: Comparing 2D patterns of protein spots
- Applications of random sampling in computational geometry. II
- Union and split operations on dynamic trapezoidal maps
- On-line construction of the upper envelope of triangles and surface patches in three dimensions
- Randomized geometric algorithms and pseudorandom generators
- Fast segment insertion and incremental construction of constrained Delaunay triangulations
- Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees
- From proximity to utility: a Voronoi partition of Pareto optima
- scientific article; zbMATH DE number 3945344 (Why is no real title available?)
- The entropy of backwards analysis
- Metric spaces with expensive distances
- Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology
- A unified approach to tail estimates for randomized incremental construction
- A combinatorial bound for linear programming and related problems
- A tail estimate for Mulmuley's segment intersection algorithm
- scientific article; zbMATH DE number 7053310 (Why is no real title available?)
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- Markov incremental constructions
- On lazy randomized incremental construction
- Deletion in abstract Voronoi diagrams in expected linear time and related problems
- Efficient randomized incremental algorithm for the closest pair problem using Leafary trees
- Fast skeleton construction
- Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
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)