Chapitre 2 - Structures de données
- Terminologie et fonctionnalités des structures fondamentales
- Les arbres équilibrés
- Dictionnaire sur un univers fini
- Exercices
- Notes bibliographiques

Chapitre 3 - Méthodes déterministes pour la géométrie
- Division-fusion
- Algorithmes de balayage
- Cloisonnement
- Exercices
- Notes bibliographiques

Chapitre 4 - Echantillonnage aléatoire
- Définitions
- Les théorèmes probabilistes
- Exercices
- Notes bibliographiques

Chapitre 5 - Algorithmes randomisés
- La méthode incrémentale randomisée
- Algorithmes statiques
- Algorithmes en ligne
- Algorithmes incrémentaux accélérés
- Exercices
- Notes bibliographiques

Chapitre 6 - Algorithmes randomisés dynamiques
- Modèle probabiliste
- Le graphe d'influence augmenté
- Analyse randomisée des algorithmes dynamiques
- Exemple : cloisonnement de segments dynamique
- Exercices
- Notes bibliographiques

Deuxième partie - Enveloppe convexe

Chapitre 7 - Polytopes
- Définitions
- Combinatoire des polytopes
- Polytopes projectifs, polytopes non bornés
- Exercices
- Notes bibliographiques

Chapitre 8 - Enveloppe convexe incrémentale
- Représentation d'un polytope
- Borne inférieure
- Lemmes géométriques
- Algorithme déterministe
- Enveloppe convexe en ligne
- Enveloppe convexe dynamique
- Exercices
- Notes bibliographiques

Chapitre 9 - Enveloppes convexes en dimensions 2 et 3
- Représentation des 2- et 3-polytopes
- Enveloppe convexe par division-fusion en dimension 2
- Enveloppe convexe par division-fusion en dimension 3
- Enveloppe convexe d'une ligne polygonale
- Exercices
- Notes bibliographiques

Chapitre 10 - Programmation linéaire
- Définitions
- Programmation linéaire randomisée
- Enveloppe convexe par effeuillage
- Exercices
- Notes bibliographiques

Troisième partie - Triangulations

Chapitre 11 - Complexes et triangulations
- Définitions
- Combinatoire des triangulations
- Représentation des complexes, dualité
- Exercices
- Notes bibliographiques

Chapitre 12 - Triangulations en dimension 2
- Triangulation d'un ensemble de points
- Triangulations contraintes
- Cloisonnement et triangulation d'un polygone
- Exercices
- Notes bibliographiques

Chapitre 13 - Triangulations en dimension 3
- Triangulation d'un ensemble de points
- Triangulations contraintes
- Cloisonnement et décomposition simpliciale
- Exercices
- Notes bibliographiques

Quatrième Partie - Arrangements

Chapitre 14 - Arrangements d'hyperplans
- Définitions
- Propriétés combinatoires
- Théorème de la zone
- Construction incrémentale d'un arrangement
- Niveaux dans les arrangements d'hyperplans
- Exercices
- Notes bibliographiques

Chapitre 15 - Arrangements de segments dans le plan
- Faces d'un arrangement
- Suites de Davenport-Schinzel
- Enveloppes inférieures
- Une cellule dans un arrangement de segments de droite
- Exercices
- Notes bibliographiques

Chapitre 16 - Arrangements de triangles
- Faces d'un arrangement
- Cloisonnement des arrangements de triangles
- Enveloppe inférieure de triangles
- Une cellule dans un arrangement de triangle
- Exercices
- Notes bibliographiques

Cinquième partie Diagrammes de Voronoï

Chapitre 17 - Métriques non euclidiennes
- Définition
- Diagrammes de Voronoï et polytopes
- Complexe de Delaunay
- Diagrammes de Voronoï d'ordres supérieurs
- Exercices
- Notes bibliographiques

Chapitre 18 - Diagrammes plans
- Diagrammes de puissance
- Diagrammes affines
- Diagrammes pondérés
- Métriques L_1 et L_infini
- Diagrammes de Voronoï hyperboliques
- Exercices
- Notes bibliographiques

Chapitre 19 -
- Un algorithme par balayage
- Diagramme de Voronoï de segments de droite
- Le cas de points répartis dans deux plans
- Exercices
- Notes bibliographiques

Bibliographie

Notations

Index