Four results on randomized incremental constructions (Q686138)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Four results on randomized incremental constructions
scientific article

    Statements

    Four results on randomized incremental constructions (English)
    0 references
    0 references
    0 references
    0 references
    1 November 1993
    0 references
    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.
    0 references
    expected behavior
    0 references
    convex hull
    0 references
    space complexity
    0 references
    randomized incremental algorithm
    0 references
    0 references

    Identifiers