ABSTRACT

Randomization as an algorithmic technique goes back at least to the seventies. In a seminal paper published in 1976, Rabin uses randomization to solve a geometric problem, giving an algorithm for the closest-pair problem with expected linear running time [[Rab76]]. Randomized and probabilistic algorithms and constructions were applied successfully in many areas of theoretical computer science. Following influential work in the mid-1980s, a significant proportion of published research in computational geometry employed randomized algorithms or proof techniques. Even when both randomized and deterministic algorithms of comparable asymptotic complexity are available, the randomized algorithms are often much simpler and more efficient in an actual implementation. In some cases, the best deterministic algorithm known for a problem has been obtained by “derandomizing” a randomized algorithm.