Towards Dynamic Randomized Algorithms in Computational Geometry

摘要

Computational geometry aims to design and analyze algorithms for solvinggeometric problems. Randomization allows the use of complicated data structures to be avoided, and was proved to be very efficient, from both points of view of theoretical complexity and practical results. Particular interest is shown in designing dynamic algorithms: in practice, the data of a problem are often acquired progressively. It is obviously not reasonable to compute the whole result again each time a new data is inserted, (semi)dynamic schemes are thus necessary. A very general data structure, the Influence Graph, is introduced, that allows the construction of various geometric structures: Voronoi diagrams, arrangements of line segments, etc. Both theoretical complexity and practical efficiency of the algorithms are studied.