Towards dynamic randomized algorithms in computational geometry (Q1310282)

Randomized algorithms have been introduced to computational geometry about ten years ago. They allow many geometric structures, like e.g. Voronoi diagrams, Delaunay triangulations, convex hulls, and arrangements, to be constructed in an incremental way, by inserting the underlying points, huperplanes etc. one by one into a structure already computed. The total time such a computation takes does in general depend on the order in which the objects are inserted. The time performance of a randomized algorithm is measured by the expected running time, where the average is taken over all \(n!\) many orders of inserting \(n\) objects. This approach leads to simple algorithms for difficult problems, that often achieve the same time performance as worst-case optimal algorithms do (which are, in general, more complicated). The analysis of randomized algorithms looked quite miraculous, ten years ago. Meanwhile, the constant effort of several researchers has helped to clarify and to simplify the proofs. Monique Teillaud's book -- her doctoral thesis- nicely describes the development until 1991, and presents interesting generalizations. Upon inserting a new object into a structure already constructed, some parts of the structure must be changed because they are ``in conflict'' with the object newly inserted. Performance depends upon how fast the new object's location and the conflicting old parts can be found. Originally, a conflict graph had to be maintained that stores all conflicts between the structure so far constructed and all objects not yet inserted. This requires a static environment where the set of objects is fully known in advance. Boissonnat's and Teillaud's Delaunay tree was the ancestor of the influence graph, a more flexible solution which allows for insertion of arbitrary objects not previously known. Roughly, the influence graph consists of all the old structures so far generated, suitably placed on top of each other. It is shown that for Delaunay triangulations and for arrangements of line segments the influence graph can be dynamized to handle deletions of objects previously inserted. Also, the Delaunay tree is generalized to include order-\(k\) tessellations in higher dimensions. Since this book has appeared, the analysis of randomized algorithms has been further simplified. The interested reader should consult e.g. the paper by Clarkson, Mehlhorn, and Seidel ``Four results on randomized incremental construction'' in Comput. Geom. 3, No. 4, 185-212 (1993; Zbl 0781.68112)].