Notes on Convex Sets, Polytopes, Polyhedra Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Notes on Convex Sets, Polytopes, Polyhedra Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations

Jean Gallier
  • Fonction : Auteur
  • PersonId : 844977

Résumé

Des outils mathématiques de base tels que les ensembles convexes, les polytopes et la topologie combinatoire, sont beaucoup utilisés en modélisation géométrique, vision, maillage, imagerie médicale et robotique. Ce rapport peut être considéré comme un tutorial et un ensemble de notes sur les ensembles convexes, les polytopes, les polyhèdres, la topologie combinatoire, les diagrames de Voronoi et les triangulations de Delaunay. Il est destiné à une large audience ayant une inclination mathématique. Une de mes motivations (egoïste!) en rédigeant ces notes était de comprendre le concept d'{\it éffeuillage\/} et de voir comment il est utilisé pour démontrer la célèbre formule d'Euler-Poincaré (Poincaré, 1899) et le plus récent {\it Théorème de la borne supérieure\/} (McMullen, 1970) pour les polytopes. Une autre de mes motivations était de donner un traitement ``correct'' des triangulations de Delaunay et des diagrames de Voronoi à partir des projections stéréographiques (directes et inverses) sur une sphère. Je prouve rigoureusement que l'application qui transforme la sphère (projective) en un paraboloïde (projectif) a un comportement correct, c'est-à-dire, fait correspondre la triangulation de Delaunay et le diagrame de Voronoi par rapport au relèvement sur la sphère à la triangulation de Delaunay et au diagrame de Voronoi par rapport au relèvement traditionel sur le paraboloïde. Le problème est que cette correspondence n'est bien définie (totale) que dans l'espace projectif et nous sommes donc obligés de définir la notion de polyhèdre convexe dans l'espace projectif. Il s'avère que pour atteindre nos objectifs (même partiellement), j'ai trouvé nécessaire d'inclure une revue de certaines notions de base telles que les ensembles convexes, les polytopes, les polyhèdres et les espaces projectifs. J'ai inclu un traitement assez détaillé de l'équivalence des $V$-polytopes et des $H$-polytopes ainsi que l'équivalence des $V$-polyhèdres et des $H$-polyhèdres, qui est un peu plus difficile. En particulier, la méthode {\it d'élimination de Fourier-Motzkin\/} (une version de la méthode de l'élimination Gaussienne pour les inégalités) est traitée en détail. J'ai du également inclure un traitement des espaces projectifs, des applications projectives et de la dualité polaire par rapport à une quadrique non dégénérée afin de définir une notion convenable de ``polyhèdre projectif'' reposant sur les cones. Il nous semble que cette notion de polyhèdre projectif est originale. Nous pensons également que certaines des preuves établissant l'équivalence des $V$-polyhèdres et des $H$-polyhèdres sont originales.
Fichier principal
Vignette du fichier
convex-RR.pdf (1.21 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00193831 , version 1 (04-12-2007)
inria-00193831 , version 2 (05-12-2007)
inria-00193831 , version 3 (05-12-2007)

Identifiants

  • HAL Id : inria-00193831 , version 1

Citer

Jean Gallier. Notes on Convex Sets, Polytopes, Polyhedra Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations. [Research Report] 2007, pp.194. ⟨inria-00193831v1⟩
266 Consultations
130 Téléchargements

Partager

Gmail Facebook X LinkedIn More