Transcription

Notes on Convex Sets, Polytopes, Polyhedra,Combinatorial Topology, Voronoi Diagrams andDelaunay TriangulationsJean Gallier and Jocelyn QuaintanceDepartment of Computer and Information ScienceUniversity of PennsylvaniaPhiladelphia, PA 19104, USAe-mail: [email protected] 20, 2017

2

3Notes on Convex Sets, Polytopes, Polyhedra, CombinatorialTopology, Voronoi Diagrams and Delaunay TriangulationsJean GallierAbstract: Some basic mathematical tools such as convex sets, polytopes and combinatorialtopology, 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 aset of notes on convex sets, polytopes, polyhedra, combinatorial topology, Voronoi Diagramsand Delaunay Triangulations. It is intended for a broad audience of mathematically inclinedreaders.One of my (selfish!) motivations in writing these notes was to understand the conceptof 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 mymotivations was to give a “correct” account of Delaunay triangulations and Voronoi diagramsin terms of (direct and inverse) stereographic projections onto a sphere and prove rigorouslythat the projective map that sends the (projective) sphere to the (projective) paraboloidworks correctly, that is, maps the Delaunay triangulation and Voronoi diagram w.r.t. thelifting onto the sphere to the Delaunay diagram and Voronoi diagrams w.r.t. the traditionallifting onto the paraboloid. Here, the problem is that this map is only well defined (total) inprojective space and we are forced to define the notion of convex polyhedron in projectivespace.It turns out that in order to achieve (even partially) the above goals, I found that it wasnecessary to include quite a bit of background material on convex sets, polytopes, polyhedraand projective spaces. I have included a rather thorough treatment of the equivalence ofV-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 ofGaussian elimination for inequalities) is discussed in some detail. I also had to include somematerial on projective spaces, projective maps and polar duality w.r.t. a nondegeneratequadric in order to define a suitable notion of “projective polyhedron” based on cones. Tothe best of our knowledge, this notion of projective polyhedron is new. We also believe thatsome of our proofs establishing the equivalence of V-polyhedra and H-polyhedra are new.Key-words: Convex sets, polytopes, polyhedra, shellings, combinatorial topology, Voronoidiagrams, Delaunay triangulations.

4

Contents1 Introduction1.1 Motivations and Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 Basic Properties of Convex Sets2.1 Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 Carathéodory’s Theorem . . . . . . . . . . . . . . . . . . . .2.3 Vertices, Extremal Points and Krein and Milman’s Theorem2.4 Radon’s, Tverberg’s, Helly’s, Theorems and Centerpoints . .77.11111317223 Separation and Supporting Hyperplanes3.1 Separation Theorems and Farkas Lemma . . . . . . . . . . . . . . . . . . . .3.2 Supporting Hyperplanes and Minkowski’s Proposition . . . . . . . . . . . . .3.3 Polarity and Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .292945464 Polyhedra and Polytopes4.1 Polyhedra, H-Polytopes and V-Polytopes . . . . .4.2 The Equivalence of H-Polytopes and V-Polytopes4.3 The Equivalence of H-Polyhedra and V-Polyhedra4.4 Fourier-Motzkin Elimination and Cones . . . . . .53536264705 Projective Spaces and Polyhedra, Polar Duality5.1 Projective Spaces . . . . . . . . . . . . . . . . . .5.2 Projective Polyhedra . . . . . . . . . . . . . . . .5.3 Tangent Spaces of Hypersurfaces . . . . . . . . .5.4 Quadrics (Affine, Projective) and Polar Duality .7979869399.6 Basics of Combinatorial Topology1076.1 Simplicial and Polyhedral Complexes . . . . . . . . . . . . . . . . . . . . . . 1076.2 Combinatorial and Topological Manifolds . . . . . . . . . . . . . . . . . . . . 1197 Shellings and the Euler-Poincaré Formula1237.1 Shellings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1237.2 The Euler-Poincaré Formula for Polytopes . . . . . . . . . . . . . . . . . . . 1325

6CONTENTS7.37.4Dehn-Sommerville Equations for Simplicial Polytopes . . . . . . . . . . . . . 135The Upper Bound Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 1418 Dirichlet–Voronoi Diagrams8.1 Dirichlet–Voronoi Diagrams . . . . . . . . . . . .8.2 Triangulations . . . . . . . . . . . . . . . . . . . .8.3 Delaunay Triangulations . . . . . . . . . . . . . .8.4 Delaunay Triangulations and Convex Hulls . . . .8.5 Stereographic Projection and the Space of Spheres8.6 Stereographic Projection and Delaunay Polytopes8.7 Applications . . . . . . . . . . . . . . . . . . . . .149149156159160163181191

Chapter 1Introduction1.1Motivations and GoalsFor the past eight years or so I have been teaching a graduate course whose main goal is toexpose students to some fundamental concepts of geometry, keeping in mind their applications to geometric modeling, meshing, computer vision, medical imaging, robotics, etc. Theaudience has been primarily computer science students but a fair number of mathematicsstudents and also students from other engineering disciplines (such as Electrical, Systems,Mechanical and Bioengineering) have been attending my classes. In the past three years,I have been focusing more on convexity, polytopes and combinatorial topology, as conceptsand tools from these areas have been used increasingly in meshing and also in computationalbiology and medical imaging. One of my (selfish!) motivations 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. Anotherof my motivations was to give a “correct” account of Delaunay triangulations and Voronoidiagrams in terms of (direct and inverse) stereographic projections onto a sphere and proverigorously that the projective map that sends the (projective) sphere to the (projective)paraboloid works correctly, that is, maps the Delaunay triangulation and Voronoi diagramw.r.t. the lifting onto the sphere to the Delaunay triangulation and Voronoi diagram w.r.t.the lifting onto the paraboloid. Moreover, the projections of these polyhedra onto the hyperplane xd 1 0, from the sphere or from the paraboloid, are identical. Here, the problemis that this map is only well defined (total) in projective space and we are forced to definethe notion of convex polyhedron in projective space.It turns out that in order to achieve (even partially) the above goals, I found that it wasnecessary to include quite a bit of background material on convex sets, polytopes, polyhedraand projective spaces. I have included a rather thorough treatment of the equivalence ofV-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 ofGaussian elimination for inequalities) is discussed in some detail. I also had to include somematerial on projective spaces, projective maps and polar duality w.r.t. a nondegenerate7

8CHAPTER 1. INTRODUCTIONquadric, in order to define a suitable notion of “projective polyhedron” based on cones. Thisnotion turned out to be indispensible to give a correct treatment of the Delaunay and Voronoicomplexes using inverse stereographic projection onto a sphere and to prove rigorously thatthe well known projective map between the sphere and the paraboloid maps the Delaunaytriangulation and the Voronoi diagram w.r.t. the sphere to the more traditional Delaunaytriangulation and Voronoi diagram w.r.t. the paraboloid. To the best of our knowledge, thisnotion of projective polyhedron is new. We also believe that some of our proofs establishingthe equivalence of V-polyhedra and H-polyhedra are new.Chapter 6 on combinatorial topology is hardly original. However, most texts coveringthis material are either old fashion or too advanced. Yet, this material is used extensively inmeshing and geometric modeling. We tried to give a rather intuitive yet rigorous exposition.We decided to introduce the terminology combinatorial manifold , a notion usually referredto as triangulated manifold .A recurring theme in these notes is the process of “conification” (algebraically, “homogenization”), that is, forming a cone from some geometric object. Indeed, “conification” turnsan object into a set of lines, and since lines play the role of points in projective geometry, “conification” (“homogenization”) is the way to “projectivize” geometric affine objects.Then, these (affine) objects appear as “conic sections” of cones by hyperplanes, just the waythe classical conics (ellipse, hyperbola, parabola) appear as conic sections.It is worth warning our readers that convexity and polytope theory is deceptively simple.This is a subject where most intuitive propositions fail as soon as the dimension of the spaceis greater than 3 (definitely 4), because our human intuition is not very good in dimensiongreater than 3. Furthermore, rigorous proofs of seemingly very simple facts are often quitecomplicated and may require sophisticated tools (for example, shellings, for a correct proofof the Euler-Poincaré formula). Nevertheless, readers are urged to strenghten their geometricintuition; they should just be very vigilant! This is another case where Tate’s famous sayingis more than pertinent: “Reason geometrically, prove algebraically.”At first, these notes were meant as a complement to Chapter 3 (Properties of ConvexSets: A Glimpse) of my book (Geometric Methods and Applications, [20]). However, theyturn out to cover much more material. For the reader’s convenience, I have included Chapter3 of my book as part of Chapter 2 of these notes. I also assume some familiarity with affinegeometry. The reader may wish to review the basics of affine geometry. These can be foundin any standard geometry text (Chapter 2 of Gallier [20] covers more than needed for thesenotes).Most of the material on convex sets is taken from Berger [6] (Geometry II ). Other relevantsources include Ziegler [45], Grünbaum [24] Valentine [43], Barvinok [3], Rockafellar [34],Bourbaki (Topological Vector Spaces) [9] and Lax [26], the last four dealing with affine spacesof infinite dimension. As to polytopes and polyhedra, “the” classic reference is Grünbaum[24]. Other good references include Ziegler [45], Ewald [18], Cromwell [14] and Thomas [40].The recent book by Thomas contains an excellent and easy going presentation of poly-

1.1. MOTIVATIONS AND GOALS9tope theory. This book also gives an introduction to the theory of triangulations of pointconfigurations, including the definition of secondary polytopes and state polytopes, whichhappen to play a role in certain areas of biology. For this, a quick but very efficient presentation of Gröbner bases is provided. We highly recommend Thomas’s book [40] as furtherreading. It is also an excellent preparation for the more advanced book by Sturmfels [39].However, in our opinion, the “bible” on polytope theory is without any contest, Ziegler [45],a masterly and beautiful piece of mathematics. In fact, our Chapter 7 is heavily inspired byChapter 8 of Ziegler. However, the pace of Ziegler’s book is quite brisk and we hope thatour more pedestrian account will inspire readers to go back and read the masters.In a not too distant future, I would like to write about constrained Delaunay triangulations, a formidable topic, please be patient!I wish to thank Marcelo Siqueira for catching many typos and mistakes and for hismany helpful suggestions regarding the presentation. At least a third of this manuscript waswritten while I was on sabbatical at INRIA, Sophia Antipolis, in the Asclepios Project. Mydeepest thanks to Nicholas Ayache and his colleagues (especially Xavier Pennec and HervéDelingette) for inviting me to spend a wonderful and very productive year and for makingme feel perfectly at home within the Asclepios Project.

10CHAPTER 1. INTRODUCTION

Chapter 2Basic Properties of Convex Sets2.1Convex SetsConvex sets play a very important role in geometry. In this chapter we state and prove someof the “classics” of convex affine geometry: Carathéodory’s theorem, Radon’s theorem, andHelly’s theorem. These theorems share the property that they are easy to state, but theyare deep, and their proof, although rather short, requires a lot of creativity.Given an affine space E, recall that a subset V of E is convex if for any two pointsa, b V , we have c V for every point c (1 λ)a λb, with 0 λ 1 (λ R). Givenany two points a, b, the notation [a, b] is often used to denote the line segment between aand b, that is,[a, b] {c E c (1 λ)a λb, 0 λ 1},and thus a set V is convex if [a, b] V for any two points a, b V (a b is allowed). Theempty set is trivially convex, every one-point set {a} is convex, and the entire affine spaceE is, of course, convex.(a)(b)Figure 2.1: (a) A convex set; (b) A nonconvex set111

12CHAPTER 2. BASIC PROPERTIES OF CONVEX SETSIt is obvious that the intersection of any family (finite or infinite) of convex sets isconvex. Then, given any (nonempty) subset S of E, there is a smallest convex set containingS denoted by conv(S) or C(S), and called the convex hull