Randomized geometric algorithms and pseudorandom generators

It is shown that the bounds on the expected running times of most of the randomized incremental algorithms in computational geometry do not change by more than a constant factor when they are made pseudorandom using a very simple scheme. This reduces the number of random bits used by these algorithms from (nlogn) toO(logn).This research was supported by Packard fellowship.