MPI-INF/SWS Research Reports 1991-2021
2. Number - All Departments
MPI-I-92-112
Four results on randomized incremental constructions
Clarkson, K. L. and Mehlhorn, Kurt and Seidel, Raimund
March 1992, 21 pages.
.Status: available - back from printing
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}
-
MPI-I-92-112.pdf
- Attachement: MPI-I-92-112.pdf (16255 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1992-112
BibTeX@TECHREPORT{ClarksonMehlhornSeidel92,
AUTHOR = {Clarkson, K. L. and Mehlhorn, Kurt and Seidel, Raimund},
TITLE = {Four results on randomized incremental constructions},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-92-112},
MONTH = {March},
YEAR = {1992},
ISSN = {0946-011X},
}