Notes on Convex Sets, Polytopes, Polyhedra Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2007

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

(1)
1
Jean Gallier
  • Function : Author
  • PersonId : 844977

Abstract

Some basic mathematical tools such as convew sets, polytopes and combinatorial topology, are used quite heavily in applied fields such as geometric modeling, meshing, computer vision, medical imaging and robotics. This report may be viewed as a tutorial and a set of notes on convex sets, polytopes, polyhedra, combinatorial topology, Voronoi Diagrams and Delaynay Triangulations. It is intended for a broad audience of mathematically inclined readers. One of my (selfish!) motivations in writing these notes was to understand the concept of shelling and how it is used to prove the famous Euler-Poincaré formula (Poincaré, 1899) and the more recent Upper Bound Theorem (McMullen, 1970) for polytopes. Another of my motivations was to give a "correct" account of Delaunay triangulations and Voronoi diagrams in terms of (direct and inverse) stereographic projections onto a sphere and prove rigorously that the projective map that sends the (projective) sphere to the (projective) paraboloid works correctly, that is, maps the Delaunay triangulation and the Voronoi diagrams w.r.t. the traditional lifting onto the paraboloid. Here, the problem is that this map is only well defined (total) in projective space and we are forced to define the notion of convex polyhedron in projective space. It turns out that in order to acheve (even partially) the above goals, I found that it was necessary to include quite a bit of background material on convex sets, polytopes, polyhedra and projective spaces. I have included a rather thorough treatment of the equivalence of V-polytopes and H-polytopes and also of the equivalence of V-polyhedra and H-polyhedra, which is a bit harder. In particular, the Fourier-Motzkin elimination method (a version of Gaussian elimination for inequalities) is discussed in some detail. I also had to include some material on projective spaces, projective maps and polar duality w.r.t. a nondegenerate quadric in order to define a suitable notion of "projective polyhedron" based on cones. We also believe that some of our proofs establishing the equivalence of V-polyhedra and H-polyhedra are new.
Fichier principal
Vignette du fichier
convex-RR.pdf (1.21 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : inria-00193831 , version 3

Cite

Jean Gallier. Notes on Convex Sets, Polytopes, Polyhedra Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations. [Research Report] RR-6379, INRIA. 2007, pp.191. ⟨inria-00193831v3⟩
250 View
97 Download

Share

Gmail Facebook Twitter LinkedIn More