Computational geometry concerns itself with designing and analyzing algorithms for solving geometric problems. The field has reached a high level of sophistication, and very complicated algorithms have been designed.However, it is also useful to develop more practical algorithms, so long as they are based on rigorous methods. One such method is the use of randomized algorithms. These algorithms have become more and more popular, turning into one of the hottest areas of recent years. Dynamic algorithms are particularly interesting because in practice the data of a problem are often acquired progressively. In this monograph the author studies the theoretical complexity and practical efficiency of randomized dynamic algorithms.

Bibliographic Information

Book Title: Towards Dynamic Randomized Algorithms in Computational Geometry
Authors: Monique Teillaud
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/3-540-57503-0
Publisher: Springer Berlin, Heidelberg
eBook Packages: Springer Book Archive
Copyright Information: Springer-Verlag Berlin Heidelberg 1993
Softcover ISBN: 978-3-540-57503-0Published: 23 November 1993
eBook ISBN: 978-3-540-48202-4Published: 30 June 2005
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: XI, 169
Topics: Theory of Computation, Computer Graphics, Algorithm Analysis and Problem Complexity, Combinatorics, Geometry

Publish with us

Policies and ethics

Towards Dynamic Randomized Algorithms in Computational Geometry

Overview

Access this book

Other ways to access

Table of contents (7 chapters)

Front Matter

Fundamental structures

Static randomized incremental algorithms

The Delaunay tree

A general structure: The influence graph

The k-Delaunay tree

Towards a fully dynamic structure

Parallel work

Back Matter

Keywords

About this book

Bibliographic Information

Publish with us

Search

Navigation