Randomized algorithm: Difference between revisions

Revision as of 15:35, 12 October 2019

Revision as of 14:18, 12 November 2019

Line 85:

===Randomized incremental constructions in geometry===

In [[computational geometry]], a standard technique to build a structure like a [[convex hull]] or [[Delaunay triangulation]] is to randomly permute the input points and then insert them one by one into the existing structure. The randomization ensures that the expected number of changes to the structure caused by an insertion is small, and so the expected running time of the algorithm can be upper bounded from above. This technique is known as [[randomized incremental construction]].<ref>Seidel R. [http://www.cs.berkeley.edu/~jrs/meshpapers/Seidel.ps.gz Backwards Analysis of Randomized Geometric Algorithms].</ref>

===Min cut===