La Randomisation Permet la Construction d'Algorithmes Simples en O(N LOG* n) pourdes Problemes Lineaires Difficiles (Randomization Yields Simple O(n LOG* n) Algorithms for Difficult omega(N) Problems)

摘要

The results on the influence graph from a study on applications of randomsampling to online algorithms in computational geometry are used to adapt them for particular cases where it is possible to improve the expected randomized complexity of algorithms from O(n log n), to O(n log* n). This technique applies in the following applications: triangulation of a simple polygon, medial axis of a simple polygon, Delaunay triangulation of vertices of a convex polygon, and Delaunay triangulation of points knowing the minimum spanning tree.