To process the huge amounts of data generated by applications, it's not enough to improve computer performance; we need to design algorithms that are efficient both in theory and in practice. One of the most fruitful advances in this race for performance has been the introduction of randomness. These are known as randomized algorithms. Randomized algorithms rely on chance to avoid, at least on average, the complex configurations (generally rare) that penalize performance; they are often both simple and efficient, and are the algorithms of choice in practice. Although randomized algorithms were invented to solve geometric problems, they now occupy an important place in all areas of algorithmics.
This lecture explains the theory of randomized incremental algorithms, using the example of calculating the convex envelope of a finite set of points. Unlike the incremental algorithm presented in the first lecture, this algorithm is optimal in all dimensions and its analysis is elementary. The lecture presents other examples of randomized incremental algorithms and also shows how the central result of the theory, probabilistic in nature, leads to deterministic Combinatorics results that cannot be proved otherwise.
