Construction de partitions élémentaires de segments dans le plan

Construction de partitions élémentaires
de segments dans le plan
Mathieu Brévilliers, Nicolas Chevallier, Dominique Schmitt
Laboratoire Mathématique, Informatique et Applications
4-6, rue des Frères Lumière 68093 Mulhouse Cédex 07
RÉSUMÉ
Nous généralisons la notion de triangulation à un ensemble de points et de segments du plan qui sont disjoints. Nous
définissons des partitions élémentaires de tels ensembles et nous donnons diverses propriétés (formes des arêtes,
nombres de faces et d'arêtes) qui permettent de déduire un algorithme de construction par balayage en temps O(n log n)
à l’aide d’une structure de données adpatée. Nous définissons ensuite la partition élémentaire de Delaunay et nous
montrons qu’elle correspond au dual du diagramme de Voronoï de segments.
Mots-clés : partition élémentaire, algorithme par balayage, Delaunay, Voronoï.
1. INTRODUCTION
La triangulation d’un ensemble de points (encore appelée maillage triangulaire) est un problème classique qui a été
largement étudié en géométrie algorithmique. Ce problème admet de nombreuses applications telles que la modélisation
de surfaces. Il a été démontré que la triangulation la plus régulière d’un ensemble de points du plan est la triangulation
de Delaunay [La77]. La notion de triangulation a ensuite été généralisée à un ensemble de points et de segments avec
l’introduction de la triangulation contrainte et il a été démontré que la triangulation de Delaunay contrainte d’un
ensemble de ...