Four results on randomized incremental constructions

Clarkson, K. L.; Mehlhorn, Kurt

Local TagsRelease HistoryDetailsSummary

Four results on randomized incremental constructions

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

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-B6ED-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-002D-F194-9

Genre: Report

Files

show Files

hide Files

:

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

View Save

File Permalink:
https://hdl.handle.net/11858/00-001M-0000-0014-D06A-9

Name:
92-112_ch.pdf

Description:
-

OA-Status:

Visibility:
Public

MIME-Type / Checksum:
application/pdf / [MD5]

Technical Metadata:

View

Copyright Date:
-

Copyright Info:
-

License:
-

Locators

show

Creators

show

hide

Creators:
Clarkson, K. L.¹, Author
Mehlhorn, Kurt¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show

hide

Free keywords: -

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}

Details

show

hide

Language(s): eng - English

Dates: Date issued: 1992

Publication Status: Issued

Pages: 21 p.

Publishing info: Saarbrücken : Max-Planck-Institut für Informatik

Table of Contents: -

Rev. Type: -

Identifiers: Report Nr.: MPI-I-92-112
BibTex Citekey: ClarksonMehlhornSeidel92

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Research Report / Max-Planck-Institut für Informatik

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -