Towards Dynamic Randomized Algorithms in Computational Geometry

1. Front Matter

   PDF

2. Fundamental structures

   Pages 6-19

3. Static randomized incremental algorithms

   Pages 22-34

4. The Delaunay tree

   Pages 36-43

5. A general structure: The influence graph

   Pages 46-76

6. The k-Delaunay tree

   Pages 78-107

7. Towards a fully dynamic structure

   Pages 110-136

8. Parallel work

   Pages 138-143

9. Back Matter

   PDF

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.

• Algorithm
• Algorithmic Geometry
• Algorithmische Geometrie
• Area
• Computational Geometry
• Computergeometrie
• Dynaische Algorithmen
• Dynamic Algorithms
• Randomisierte Algorithmen
• Randomized Algorrthms
• Voroni Diagram
• Voroni Diagramm
• algorithms
• complexity
• geometry
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics