Minkowski Addition of Triangles Mireille Rousset To cite this version: Mireille Rousset. Minkowski Addltion of Triangles. Modeling and Simulation. Universit e Joseph-Fourier – Grenoble l, 1996. French. HAL Id: tel-00005017 https://tel. archives-ouvertes. fr/tel-00005017 to View subrnitted on 23 2004 HAL is a multi-discipll archive for the depos n or 149 documents, whether ey may come from teaching and researc cientific research t. The documents abroad, or from public or private research centers.
L’archive ouverte pluridisciplinaire HAL, est destin ‘ee au d’ ep-ot et • a la diffusion de documents cientifiques de niveau recherche, publi es ou non, emanant des ‘etablissements d’enseignement et de recherche fran. cais ou etrangers, des laboratoires publics ou priv ‘ es. THESE présentée par Mireille ROUSSET pour obtenir le titre de préparée au sein du laboratoire LMC-IMAG Table des matières Introduction Chapitre Polytopes et Somme de Minkowski : 1 . Rappels, définitions et notations 1 . 1 Somme de Minkowski Rappels 1 . Outils pour la somme de Minkowski de polytopes • Polytopes • Hyperplan d’appui, points d’appui et k-faces d’un polytope • Cône normal et faisceau de normales d’un polytope ?? Propriétés du faisceau de normales • Rappels sur les arrangements d’hyperplans 6 7 8 10
Rappel de la modélisation géométrique de la fabrication d’un mélange 66 2 . Faisabilité de plusieurs mélanges 2. 1 Fabrication simultanée des mélanges 2 . 2 Quelques résultats 8 69 3. Modélisation géométrique de la coexistence 70 4 . Détermination des facettes d’un convexe de 2-mélanges 4. 1 Idée de base de l’énumération des facettes 2 Enumération des facettes 4. 71 72 75 3 somme de segments, appelée zonotope, car ces polytopes ont suscités beaucoup d’intérêts.
Les zonotopes apparaissent dans des domaines d’applications tels que : – l’économie, où les productions possibles d’un groupe d’entreprises sont modélisées par un zonotope [Hi181], – les problèmes de pavages [Gr078], [Cox62]. Le terme zonoèdre (zonotope de dimension 3) a été introduit E. S. Fedorov ans le domaine de la cristallographie. L’auteur s’intéressait particulièrement aux zonoèdres qui pavent l’espace. Les zonotopes ont fait l’objet de nombreuses études qui ont révélé leurs propriétés géométriques et combinatoires.
Les principaux résultats sont apparus dans les travaux de H. S. Coxeter, E. D. Bolker, P. Mcxqullen et G. C. Shephard. Citons quelques sujets d’étude : – la caractérlsation des zonotopes par des propriétés de symétrie de leur faces, – les zones, – les types combinatoires, – les diagrammes projectifs pour les zonoèdres. Les zonotopes interviennent dans le modèle géométrique des rocédés de fabrication de mélanges. A partir de la représentation vectorielle des produits, P.
Valentin a développé le concept de convexe de mélanges. Ce convexe est un zonotope associé aux produits de base disponibles. Il représente l’ensemble des mélanges faisables, de sorte que la faisabilité d’un mélange s’exprime par l’appartenance d’un point, re résentation vectorielle du mélange, au zonotope. Cette 4 DF d’un point, représentation vectorielle du mélange, au zonotope. Cette modélisation a été à l’origine de différents travaux (cf. [Sla86], [Gir86], [Gir], [LSV91], [Lac], [sza91], [Da095]
En général, la façon de fabriquer un produit n’est pas unique, d’où l’élaboration d’un critère de gestion des mélanges. Ce critère a pour but de consommer les produits de base de façon à ce que les produits restant après fabrication du mélange permettent de fabriquer le plus grand éventail de mélanges possibles. Après avoir traité le problème d’un seul mélange, les impératifs de la fabrication ont amené à considérer la fabrication de plusieurs mélanges.
Différentes solutions ont été envisagées avec succès pour l’utilisation du modèle dans la pratique : optimisation e la fabrication d’un mélange pour préserver les opérations futures, résolutlon numérique de la fabrication de plusieurs mélanges en utilisant la programmation 2 linéaire. Pour fabriquer plusieurs mélanges, plutôt qu’une stratégie séquentielle de fabrication, où la faisabilité d’un second mélange dépend du choix fait pour la fabrication d’un premier mélange, on regarde si globalement ces mélanges sont faisables.
Ce problème est énoncé sous la forme plus générale de faisabilité est éga ement appelé problème de coexistence de deux familles de vecteurs. La modélisation géométrique de ce problème introduite dans Lac] généralise le convexe de mélanges à celui de q-mélanges. Ces nouveaux ensembles résultent de la somme de q-simplexes et la faisabilité simultanée des mélanges est équivalente à l’appartenance d’un point à ce convexe.
La faisabilité simultanée de 2 mélanges conduit à l’étude de la somme de triangles. En dehors du contexte des mélanges, il nous a paru intéressant d’étudier les sommes de triangles en tant que généralisation des sommes de segments, et d’étudier la structure de ces polytopes et des méthodes de constructions. On pourrait élargir cette étude aux sommes de simplexes. Cette voie n’a pas été abordée dans cette thèse, mais les méthodes développées pourraient certainement s’adapter.
Dans le chapitre I, on effectue des rappels sur les polytopes et on introduit les outils utilisés dans cette thèse : les faisceaux de normales, les arrangements d’hyperplans et le premier diagramme projectif, ainsi que les raffinements de faisceaux de normales qui sont fondamentaux pour la suite. On rappelle également certaines propriétés des zonotopes. Ces notions sont empruntées soit à la géométrie classique soit à la géométrie algorithmique. La somme de triangles est étudiée dans le chaptre Il.
Les résultats obtenus é combinatoire de la concernent essentielleme 5 dans le chapitre Il. Les résu tats obtenus concernent essentiellement la complexité combinatoire de la somme et sa construction. Ils s’appuient sur l’étude de la somme de polytopes faite par P. Gritzmann et B. sturrnfels (Cf. [Gri]). On montre que, comme pour les zonotopes, le nombre de faces de la somme de p triangles dans se comporte en O(pn-l) et cette complexité est atteinte. ne propriété géométrique similaire à celle des zones d’un zonotope est mise en évidence. De même qu’à un vecteur correspond une zone d’un onotope, à un triangle correspond trois « demi-zones » sur le polytope. La construction en dimension 2 ne présente pas de difficulté. Sa description nous permet d’expliquer les deux étapes de la somme. En dimension 3, la construction est plus délicate mais on se ramène à un problème dans le plan, de fusion de subdivisions convexes traité par LJ. Guibas et R. Seidel dans [Gui].
On propose, pour la construction de la somme de triangles en dimension quelconque (n>3), une méthode qui permet d’extraire la structure combinatoire du polytope (ou graphe d’incidence) d’un arrangement d’hyperplans ar des opérations de fusion de faces. La construction effective qui résulte de la méthode, permet de bien mettre en d’exemples. L’algorithme décrit en dimension 3 se généralise en dimension supérieure avec une complexité optimale en O(p n-l). Dans le chapitre Ill, la somme de triangles étudiée est issue du modèle géométrique de fabrication simultanée de deux mélanges.
La représentation vectorielle des produits dans donne un convexe de dimension 6. Cest le prolongement de l’étude menée sur les mélanges binaires (i. e. pour une représentation vectorielle des „2 produits dans ) dans [Lac&Va193]. La faisabilité s’exprime par l’appartenance d’un point au convexe de 2-mélanges, ceci à orienté notre étude vers l’énumération des facettes du convexe. Celles-ci permettent d’obtenir un système d’inégalités équivalent ? la faisabilité des deux mélanges.
Cette énumération a permis d’établir la « lecture » des facettes ? partir du premier diagramme projectif. Il en résulte également que le nombre de facettes peut atteindre O(p5) pour p produits de bases. Le cas de la sélectivité régulière, c’est à dire celui où tout vecteur n’est pas combinaison linéaire positive des autres, donne lieu à une ropriété remarquable : les mélanges M 1 et M 2 sont simultanément faisables si et seulement si chacun des M 2 etM1 + M2 est 8 149 O(p2) facettes.
Cette simplification avait déjà été observée dans la fabrication d’un seul mélange, et interprétée par une dégénérescence du zonoèdre [Lac&Sza96]. Dans le chapitre IV, on aborde le sujet de la décomposition d’un polytope en somme de polytopes. On donne un aperçu des résultats existants. Dans le plan tout polygone convexe peut s’écrire comme la somme de segments et de triangles. En dimension supérieure le problème de décomposition est eaucoup plus complexe On propose une expression de la « soustraction » à un convexe d’un de ses sommandes, sous forme d’intersection de translatés.
Et on tente d’examiner ce que cette expression peut apporter du point de vue algorithmique. Polytopes et Somme de Minkwoski : Rappels Chapitre polytopes et Somme de Minkowski Les polytopes convexes ont donné lieu à de nombreuses études. Elles portent sur des aspects combinatoires et géométriques, ou encore sur des problèmes de pavage par des polytopes. On trouvera dans les ouvrages suivants un éventail des problèmes abordés : B. Grunbaum [Gru63 p. McMullen & C. C. Shephard [MCM] et 9 L’exemple des zonotopes donne une illustration des problèmes traités.
La première partie est consacrée à des rappels sur les polytopes et sur les outils liés à la somme de Minkowski de polytopes. La plupart des notions décrites sont spécifiques au cas des polytopes convexes, dans lequel notre problème se pose . hyperplan d’appui, et faisceau de normales. Le principal outil de notre étude est le faisceau de normales d’un polytope qui permettra de calculer la somme de polytopes avec sa géométrie et sa combinatoire. Cest un complexe polyédrique particulier. Il permet de ramener la somme de polytopes au calcul du raffinement commun de faisceaux de normales.
Dans la seconde partie, nous présentons les zonotopes, cas particulier de la somme de Minkowski, abondamment étudié par les géomètres. Les prlncpaux résultats sont la caractérisation des zonotopes par des propriétés géométriques de leurs faces, leur lien avec les arrangements d’hyperplans (outil usuel de la géométrie algorithmique), et les diagrammes projectifs associés aux zonoèdres. Dans tout ce qui suit, an se place dans l’espace produit scalaire Euclidien usuel noté . ê n de dimension n, muni du ID OF
