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

      0 references
      11 November 1993
      0 references
      randomized algorithms
      0 references
      computational geometry
      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

      Identifiers