No label defined (Q4023736)

It is quite well known that the dynamic maintenance of a geometric data structure is usually much more difficult than just building the same structure for a given static set of geometric objects. There are some standard dynamization techniques already known, however in practice often simple, easy to code solution efficient on the average under a reasonable assumption is sufficient. It appears that these requirements can be fulfilled by using randomized incremental algorithms. These algorithms are based on the incremental construction of an appropriate data structure in such a way that updating behaves well on the average only, where the average is taken over all possible random updata sequences as input sequences. In the thesis the randomized incremental paradigm applied to the problem of the dynamic maintenance of convex polytopes and of point location structures is studied. Essential ideas of this approach are explained with the help of a couple of examples in the introductory section, followed by a formal model for random update sequences. In subsequent sections problems of maintaining three-dimensional convex hulls, maintaining higher dimensional convex polytopes, static and dynamic ray shooting in convex polytopes and arrangements of hyperplanes, as well as random update sequences in an abstract model of geometric structures are investigated. In all sections a proper mix of informal explanation of algorithms and precise formal analysis of their behavior contributes to the clarity and readability of the presentation. At the end an one-page summary of the results in four languages (English, French, Flemish, and German) is given.