ON LAZY RANDOMIZED INCREMENTAL CONSTRUCTION

We introduce a new type of randomized incremental algorithms. Contrary to standard randomized incremental algorithms, these lazy randomized incremental algorithms are suited for computing structures that have a ''nonlocal'' definition. In order to analyze these algorithms we gene ralize some results on random sampling to such situations. We apply ou r techniques to obtain efficient algorithms for the computation of sin gle cells in arrangements of segments in the plane, single cells in ar rangements of triangles in space, and zones in arrangements of hyperpl anes.