Backwards analysis of randomized geometric algorithms (Q3138743)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 431985
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Backwards analysis of randomized geometric algorithms |
scientific article; zbMATH DE number 431985 |
Statements
11 November 1993
0 references
randomized algorithms
0 references
computational geometry
0 references
0.91620517
0 references
0.8931811
0 references
0.88632333
0 references
0.8777626
0 references
0 references
Backwards analysis of randomized geometric algorithms (English)
0 references
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].
0 references