Four results on randomized incremental constructions (Q686138)

Some aspects of randomized incremental constructions are studied. Particularly, the expected behavior of the randomized incremental construction under insertions and deletions is analyzed and the results are then applied to the problem of maintaining the convex hull in the \(d\)-dimensional space. Moreover a tail estimate for the space complexity (size of the history) of randomized incremental constructions is derived. Also a two-player game related to the randomized incremental constructions is outlined. In this game one player models the process which generates the insertion sequence, while the other player models the randomized incremental algorithm. Deterministic as well as randomized strategies for the first player are considered, and for both cases a lower bound on the complexity of the game is proved.