Four results on randomized incremental constructions

Clarkson, K. L.; Mehlhorn, Kurt

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

Four results on randomized incremental constructions

MPS-Authors

Clarkson, K. L.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

92-112_ch.pdf
(Any fulltext), 16MB

Supplementary Material (public)

There is no public supplementary material available

Citation

Clarkson, K. L., & Mehlhorn, K.(1992). Four results on randomized incremental constructions (MPI-I-92-112). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B6ED-F

Abstract

We prove four results on randomized incremental constructions (RICs): \begin{itemize} \item an analysis of the expected behavior under insertion and deletions, \item a fully dynamic data structure for convex hull maintenance in arbitrary dimensions, \item a tail estimate for the space complexity of RICs, \item a lower bound on the complexity of a game related to RICs. \end{itemize}