Skip to Main content Skip to Navigation
Reports

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

Jean Gallier 1
1 ASCLEPIOS - Analysis and Simulation of Biomedical Images
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00193831
Contributor : Jean Gallier Connect in order to contact the contributor
Submitted on : Tuesday, December 4, 2007 - 4:38:38 PM
Last modification on : Thursday, January 17, 2019 - 1:48:03 PM
Long-term archiving on: : Monday, April 12, 2010 - 6:05:41 AM

File

convex-RR.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00193831, version 1
`

Citation

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

Share

Metrics

Record views

21

Files downloads

8