Добірка наукової літератури з теми "Combinatoire géométrique"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Combinatoire géométrique".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Combinatoire géométrique":
1
Ferenczi, Sébastien. "Les transformations de Chacon : combinatoire, structure géométrique, lien avec les systèmes de complexité $2n+1$." Bulletin de la Société mathématique de France 123, no. 2 (1995): 271–92. http://dx.doi.org/10.24033/bsmf.2260.
2
Le Roux, Brigitte. "Inférence combinatoire en analyse géométrique des données." Mathématiques et sciences humaines, no. 144 (December 1, 1998). http://dx.doi.org/10.4000/msh.2781.
3
Ceballos, Cesar, Jean-Philippe Labbé, and Christian Stump. "Multi-cluster complexes." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AR,..., Proceedings (January 1, 2012). http://dx.doi.org/10.46298/dmtcs.3014.
Анотація:
International audience We present a family of simplicial complexes called \emphmulti-cluster complexes. These complexes generalize the concept of cluster complexes, and extend the notion of multi-associahedra of types ${A}$ and ${B}$ to general finite Coxeter groups. We study combinatorial and geometric properties of these objects and, in particular, provide a simple combinatorial description of the compatibility relation among the set of almost positive roots in the cluster complex. Nous présentons une famille de complexes simpliciaux appelés \emphcomplexes des multi-amas. Ces complexes généralisent le concept de complexes des amas et étendent la notion de multi-associaèdre de type ${A}$ et ${B}$ aux groupes de Coxeter finis. Nous étudions des propriétés combinatoires et géométriques de ces objets et, en particulier nous fournissons une description combinatoire simple de la relation de compatibilité sur l'ensemble des racines presque positives du complexe des amas.
4
Aguiar, Marcelo, and Kile T. Petersen. "The module of affine descents." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AS,..., Proceedings (January 1, 2013). http://dx.doi.org/10.46298/dmtcs.12811.
Анотація:
The goal of this paper is to introduce an algebraic structure on the space spanned by affine descent classes of a Weyl group, by analogy and in relation to the structure carried by ordinary descent classes. The latter classes span a subalgebra of the group algebra, Solomon's descent algebra. We show that the former span a left module over this algebra. The structure is obtained from geometric considerations involving hyperplane arrangements. We provide a combinatorial model for the case of the symmetric group. Le but de cet article est d’introduire une structure algébrique sur l’espace engendré par les classes de descente affines d’un groupe de Weyl, par rapport à la structure possédée par les classes de descente finies. Ces dernières engendrent une sous-algèbre de l’algèbre de groupe, l’algèbre de Solomon. Nous montrons que les premières engendrent un module à gauche sur cette algèbre. La structure est obtenue par moyens géométriques impliquant desarrangements d’hyperplans. Un modèle combinatoire est fourni pour le cas du groupe symétrique.
5
Beazley, Elizabeth T. "Maximal Newton polygons via the quantum Bruhat graph." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AR,..., Proceedings (January 1, 2012). http://dx.doi.org/10.46298/dmtcs.3092.
Анотація:
International audience This paper discusses a surprising relationship between the quantum cohomology of the variety of complete flags and the partially ordered set of Newton polygons associated to an element in the affine Weyl group. One primary key to establishing this connection is the fact that paths in the quantum Bruhat graph, which is a weighted directed graph with vertices indexed by elements in the finite Weyl group, encode saturated chains in the strong Bruhat order on the affine Weyl group. This correspondence is also fundamental in the work of Lam and Shimozono establishing Peterson's isomorphism between the quantum cohomology of the finite flag variety and the homology of the affine Grassmannian. In addition, using some geometry associated to the poset of Newton polygons, one obtains independent proofs for several combinatorial statements about paths in the quantum Bruhat graph and its symmetries, which were originally proved by Postnikov using the tilted Bruhat order. An important geometric application of this work is an inequality which provides a necessary condition for non-emptiness of certain affine Deligne-Lusztig varieties in the affine flag variety. Cet article étudie une relation surprenante entre la cohomologie quantique de la variété de drapeaux complets et l'ensemble partiellement ordonné de polygones de Newton associé à un élément du groupe de Weyl affine. L’élément clé pour établir cette connexion est le fait que les chemins dans le graphe de Bruhat quantique, qui est un graphe orienté pondéré dont les sommets sont indexés par des éléments du groupe de Weyl fini, encodent des chaînes saturées dans l'ordre de Bruhat fort sur le groupe de Weyl affine. Cette correspondance est aussi fondamentale dans les travaux de Lam et Shimonozo qui établissent l'isomorphisme de Peterson entre la cohomologie quantique de la variété de drapeaux finie et l'homologie de la Grassmannienne affine. De plus, en utilisant la géométrie associée à l'ensemble partiellement ordonné des polygones de Newton, on obtient des preuves indépendantes pour plusieurs assertions combinatoires sur les chemins dans le graphe de Bruhat quantiques et les symétries de ce graphe, qui ont été originellement démontrées par Postnikov en utilisant l'ordre de Bruhat incliné. Une application géométrique importante de ce travail est une inégalité qui donne une condition nécessaire pour que certaines variétés de Deligne-Lusztig affines dans la variété de drapeaux affine soient non-vides.
6
Jones, Brant. "Deodhar Elements in Kazhdan-Lusztig Theory." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AJ,..., Proceedings (January 1, 2008). http://dx.doi.org/10.46298/dmtcs.3645.
Анотація:
International audience The Kazhdan-Lusztig polynomials for finite Weyl groups arise in representation theory as well as the geometry of Schubert varieties. It was proved very soon after their introduction that they have nonnegative integer coefficients, but no simple all positive interpretation for them is known in general. Deodhar has given a framework, which generally involves recursion, to express the Kazhdan-Lusztig polynomials in a very attractive form. We use a new kind of pattern-avoidance that can be defined for general Coxeter groups to characterize when Deodhar's algorithm yields a non-recursive combinatorial formula for Kazhdan-Lusztig polynomials $P_{x,w}(q)$ of finite Weyl groups. This generalizes results of Billey-Warrington which identified the $321$-hexagon-avoiding permutations, and Fan-Green which identified the fully-tight Coxeter groups. We also show that the leading coefficient known as $\mu (x,w)$ for these Kazhdan―Lusztig polynomials is always either $0$ or $1$. Finally, we generalize the simple combinatorial formula for the Kazhdan―Lusztig polynomials of the $321$-hexagon-avoiding permutations to the case when $w$ is hexagon avoiding and maximally clustered. Les polynômes de Kazhdan-Lusztig $P_{x,w}(q)$ des groupes de Weyl finis apparaissent en théorie des représentations, ainsi qu’en géométrie des variétés de Schubert. Il a été démontré peu après leur introduction qu’ils avaient des coefficients entiers positifs, mais on ne connaît toujours pas d’interprétation combinatoire simple de cette propriété dans le cas général. Deodhar a proposé un cadre donnant un algorithme, en général récursif, calculant des formules attractives pour les polynômes de Kazhdan-Lusztig. Billey-Warrington ont démontré que cet algorithme est non récursif lorsque$w$ évite les hexagones et les $321$ et qu’il donne des formules combinatoires simples. Nous introduisons une notion d’évitement de schémas dansles groupes de Coxeter quelconques nous permettant de généraliser les résultats de Billey-Warrington à tout groupe de Weyl fini. Nous montrons que le coefficient de tête $\mu (x,w)$ de ces polynômes de Kazhdan-Lusztig est toujours $0$ ou $1$. Cela généralise aussi des résultats de Fan-Greenqui identifient les groupes de Coxeter complètement serrés. Enfin, en type $A$, nous obtenons une classe plus large de permutations évitant la récursion.
7
Bürgisser, Peter, and Christian Ikenmeyer. "A max-flow algorithm for positivity of Littlewood-Richardson coefficients." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AK,..., Proceedings (January 1, 2009). http://dx.doi.org/10.46298/dmtcs.2749.
Анотація:
International audience Littlewood-Richardson coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the general linear group $\mathrm{GL}(n,\mathbb{C})$. They have a wide variety of interpretations in combinatorics, representation theory and geometry. Mulmuley and Sohoni pointed out that it is possible to decide the positivity of Littlewood-Richardson coefficients in polynomial time. This follows by combining the saturation property of Littlewood-Richardson coefficients (shown by Knutson and Tao 1999) with the well-known fact that linear optimization is solvable in polynomial time. We design an explicit $\textit{combinatorial}$ polynomial time algorithm for deciding the positivity of Littlewood-Richardson coefficients. This algorithm is highly adapted to the problem and it is based on ideas from the theory of optimizing flows in networks. Les coefficients de Littlewood-Richardson sont les multiplicités dans la décomposition du produit tensoriel de deux représentations irréductibles du groupe général linéaire $\mathrm{GL}(n,\mathbb{C})$. Ces coefficients ont plusieurs interprétations en combinatoire, en théorie des représentations et en géométrie. Mulmuley et Sohoni ont observé qu'on peut décider si un coefficient de Littlewood-Richardson est positif en temps polynomial. C'est une conséquence de la propriété de saturation des coefficients de Littlewood-Richardson (démontrée par Knutson et Tao en 1999) et le fait bien connu que la programmation linéaire est possible en temps polynomial. Nous décrivons un algorithme $\textit{combinatoire}$ pour décider si un coefficient de Littlewood-Richardson est positif. Cet algorithme est bien adapté au problème et il utilise des idées de la théorie des flots maximaux sur des réseaux.
8
Iriarte Giraldo, Benjamin. "Dissimilarity Vectors of Trees and Their Tropical Linear Spaces (Extended Abstract)." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AO,..., Proceedings (January 1, 2011). http://dx.doi.org/10.46298/dmtcs.2918.
Анотація:
International audience We study the combinatorics of weighted trees from the point of view of tropical algebraic geometry and tropical linear spaces. The set of dissimilarity vectors of weighted trees is contained in the tropical Grassmannian, so we describe here the tropical linear space of a dissimilarity vector and its associated family of matroids. This gives a family of complete flags of tropical linear spaces, where each flag is described by a weighted tree. Nous étudions les propriétés combinatoires des arbres pondérés avec le formalisme de la géométrie tropicale et des espaces linéaires tropicaux. L'ensemble de vecteurs de dissimilarité des arbres pondérés est contenu dans la grassmannienne tropicale, donc nous décrivons ici l'espace linéaire tropical d'un vecteur de dissimilarité et sa famille de matroïdes associée. Cela permet d'obtenir une famille de drapeaux complets d'espaces linéaires tropicaux, où chaque drapeau est décrit par un arbre pondéré.
9
Colmenarejo, Laura. "Stability properties of Plethysm: new approach with combinatorial proofs (Extended abstract)." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (January 1, 2015). http://dx.doi.org/10.46298/dmtcs.2526.
Анотація:
International audience Plethysm coefficients are important structural constants in the theory of symmetric functions and in the representations theory of symmetric groups and general linear groups. In 1950, Foulkes observed stability properties: some sequences of plethysm coefficients are eventually constants. Such stability properties were proven by Brion with geometric techniques and by Thibon and Carré by means of vertex operators. In this paper we present a newapproach to prove such stability properties. This new proofs are purely combinatorial and follow the same scheme. We decompose plethysm coefficients in terms of other plethysm coefficients (related to the complete homogeneous basis of symmetric functions). We show that these other plethysm coefficients count integer points in polytopes and we prove stability for them by exhibiting bijections between the corresponding sets of integer points of each polytope. Les coefficients du pléthysme sont des constantes de structure importantes de la théorie des fonctions symétriques, ainsi que de la théorie de la représentation des groupes symétriques et des groupes généraux linéaires. En 1950, Foulkes a observé pour ces coefficients de phénomènes de stabilité: certaines suites de coefficients du pléthysme sont stationnaires. De telles propriétés ont été démontrées par Brion, au moyen de techniques géométriques, et par Thibon et Carré, au moyen d’opérateurs vertex. Dans ce travail, nous présentons une nouvelle approche, purement combinatoire, pour démontrer des propriétés de stabilité de ce type. Nous décomposons les coefficients du pléthysme comme somme alternées de coefficients de pléthysme d’un autre type (liés à la base des fonctions symétriques sommes complètes), qui comptent les points entiers dans des polytopes. Nous démontrons la stabilité des suites de ces coefficients en exhibant des bijections entres les ensembles de points entiers des polytopes correspondants.
10
Lenz, Matthias. "Hierarchical Zonotopal Power Ideals." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AO,..., Proceedings (January 1, 2011). http://dx.doi.org/10.46298/dmtcs.2939.
Анотація:
International audience Zonotopal algebra deals with ideals and vector spaces of polynomials that are related to several combinatorial and geometric structures defined by a finite sequence of vectors. Given such a sequence $X$, an integer $k \geq -1$ and an upper set in the lattice of flats of the matroid defined by $X$, we define and study the associated $\textit{hierarchical zonotopal power ideal}$. This ideal is generated by powers of linear forms. Its Hilbert series depends only on the matroid structure of $X$. It is related to various other matroid invariants, $\textit{e. g.}$ the shelling polynomial and the characteristic polynomial. This work unifies and generalizes results by Ardila-Postnikov on power ideals and by Holtz-Ron and Holtz-Ron-Xu on (hierarchical) zonotopal algebra. We also generalize a result on zonotopal Cox modules due to Sturmfels-Xu. La théorie de l'algèbre "zonotopique'' s'occupe d'idéaux et d'espaces vectoriels de polynômes qui ont un rapport avec plusieurs structures combinatoires et géométriques définies par des suites finies de vecteurs. Étant donné une telle suite $X$, un nombre entier $k \geq -1$ et un ensemble supérieur dans le treillis des plans du matroïde défini par $X$, nous définissons et étudions l'$\textit{idéal hiérarchique zonotopique}$, engendré par des puissances de formes linéaires. Sa série de Hilbert dépend seulement de la structure matroïdale de $X$. Il existe des relations avec d'autres invariants de matroïdes, tels que le polynôme d'épluchage et le polynôme caractéristique. Ce travail unifie et généralise des résultats d'Ardila-Postnikov sur les idéaux de puissances et de Holtz-Ron et Holtz-Ron-Xu sur l'algèbre zonotopique (hiérarchique). Nous généralisons aussi un résultat sur les modules de Cox zonotopiques, dû à Sturmfels-Xu.
Дисертації з теми "Combinatoire géométrique":
1
Sage, Marc. "Combinatoire algébrique et géométrique des nombres de Hurwitz." Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00804228.
Анотація:
Ce mémoire se veut une synthèse, destinée à la communauté combinatoricienne, de quelques outils développés pour aborder le problème d'Hurwitz ainsi qu'une présentation des résultats récoltés. Le problème d'Hurwitz consiste à évaluer, dans un groupe symétrique, le nombre (dit d'Hurwitz) de factorisations transitives de la permutation identité dont on a imposé le type cyclique des facteurs. Nous décrivons tout d'abord les origines topologiques de ce problème à travers le dénombrement des revêtements ramifiés de la sphère. Nous présentons également un cadre algébrique naturel, le monoïde des permutations scindées, qui permet d'exprimer les nombres d'Hurwitz comme coefficients de structure de l'algèbre de ce monoïde, plus précisément de la sous-algèbre engendrée par les classes de conjugaison, dont une base naturelle est indexée par les multipartitions (ou partitions scindées). La théorie des représentations de cette algèbre fournit un algorithme pour calculer les nombres d'Hurwitz à une partition dont la complexité (minimale, uniforme et exponentielle) est bien meilleure que celle d'une approche naïve. Ce cadre algébrique donne par ailleurs une formule décrivant les séries d'Hurwitz à plusieurs partitions comme polynômes en les séries d'Hurwitz à une seule partition. Nous présentons secondement le cadre géométrique dans lequel s'expriment d'une part la formule ELSV, laquelle décrit les nombres d'Hurwitz à une partition comme fonctions de certaines intégrales, d'autre part un théorème de M. Kazarian exprimant les séries de Hurwitz à une partition comme polynômes en certaines séries formelles dont l'étude asymptotique est achevée. Une fois décrit le fonctionnement de ce cadre intégral, nous récoltons l'asymptotique de tous les nombres d'Hurwitz
2
Siegel, Anne. "Représentations géométrique, combinatoire et arithmétique des systèmes subsitutifs de type Pisot." Aix-Marseille 2, 2000. http://www.theses.fr/2000AIX22075.
3
Skapin, Xavier. "Utilisation du produit cartésien en modélisation géométrique 4D pour l'animation." Poitiers, 2001. http://www.theses.fr/2001POIT2301.
Анотація:
Nous travaillons sur la modélisation géométrique 4D (spatio-temporelle) pour l'animation : son intérêt est d'homogénéiser des méthodes de modélisation 3D à la dimension 4, mais ses principales difficultés sont d'interpréter un objet 4D en termes d'animation et de contrôler sa construction. Notre utilisons des objets spatio-temporels de dimension inférieure à 4 comme opérandes de l'opération de produit cartésien, pour créer des objets de dimension supérieure dont l'interprétation se déduit de celle des opérandes. Une étude de cas sur des opérandes de base a mené à une méthode d'interprétation et de contrôle des objets 4D créés par produit cartésien. Un modeleur géométrique à base topologique 4D nous a permis de créer des animations complexes. Nous avons adapté la définition du produit cartésien aux ensembles semi-simpliciaux, aux cartes généralisées, aux cartes orientées et aux chaînes de cartes fermées (à chacune de ces définitions correspond un algorithme optimal en temps de calcul)We work in the scope of 4D (space-time) modelling for animation. Extending 3D modelling methods to dimension 4 is the main advantage of 4D modelling, but interpreting a 4D object as an animation and controlling the construction of this object are the main drawbacks of 4D modelling. Our method uses space-time objects of dimension lesser than 4 as operands of the cartesian product operation to create an object of greater dimension, whose interpretation is deduced from operands'. We made a case study about cartesian product of basic operands defined as point trajectories. This study led to a method for interpreting and controlling 4D objects resulting from cartesian product. We have created a topologically-based 4D geometrical modeler, allowing us to design elaborate animations. We have adapted cartesian product operation to semi-simplicial sets, generalized maps, n-maps and closed chains of maps. Each of these definitions corresponds to an algorithm with an optimal complexity in time
4
Ledent, Jérémy. "Sémantique géométrique pour la calculabilité asynchrone." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLX099/document.
Анотація:
Le domaine des protocoles tolérants aux pannes étudie quelles tâches concurrentes sont résolubles dans différents modèles de calcul avec pannes. Des outils mathématiques basés sur la topologie combinatoire ont été développés depuis les années 1990 pour aborder ces questions. Dans ce cadre, la tâche que l’on veut résoudre, et le protocole auquel on fait appel, sont modélisés par des complexes simpliciaux chromatiques. On définit qu’un protocole résout une tâche lorsqu’il existe une certaine application simpliciale entre ces complexes.Dans cette thèse, on étudie ces méthodes géométriques du point de vue de la sémantique. Le premier objectif est de fonder cette définition abstraite de résolution d’une tâche sur une autre plus concrète, basée sur des entrelacements de traces d’exécution. On examine diverses notions de spécifications pour les objets concurrents, afin de définir un cadre général pour la résolution de tâches par des objets partagés. On montre ensuite comment extraire de ce cadre la définition topologique de résolubilité de tâches.Dans la deuxième partie de la thèse, on prouve que les complexes simpliciaux chromatiques peuvent être utilisés pour évaluer des formules de logique épistémique. Cela permet d’interpréter les preuves topologiques d’impossibilité en fonction de la quantité de connaissances à acquérir pour résoudre une tâche.Enfin, on présente quelques liens préliminaires avec la sémantique dirigée pour les programmes concurrents. On montre comment la subdivision chromatique d’un simplexe peut être retrouvée en considérant des notions combinatoires de chemins dirigésThe field of fault-tolerant protocols studies which concurrent tasks are solvable in various computational models where processes may crash. To answer these questions, powerful mathematical tools based on combinatorial topology have been developed since the 1990’s. In this approach, the task that we want to solve, and the protocol that we use to solve it, are both modeled using chromatic simplicial complexes. By definition, a protocol solves a task when there exists a particular simplicial map between those complexes.In this thesis we study these geometric methods from the point of view of semantics. Our first goal is to ground this abstract definition of task solvability on a more concrete one, based on interleavings of execution traces. We investigate various notions of specification for concurrent objects, in order to define a general setting for solving concurrent tasks using shared objects. We then show how the topological definition of task solvability can be derived from it.In the second part of the thesis, we show that chromatic simplicial complexes can actually be used to interpret epistemic logic formulas. This allows us to understand the topological proofs of task unsolvability in terms of the amount of knowledge that the processes should acquire in order to solve a task.Finally, we present a few preliminary links with the directed space semantics for concurrent programs. We show how chromatic subdivisions of a simplex can be recovered by considering combinatorial notions of directed paths
5
Philippe, Eva. "Geometric realizations using regular subdivisions : construction of many polytopes, sweep polytopes, s-permutahedra." Electronic Thesis or Diss., Sorbonne université, 2024. http://www.theses.fr/2024SORUS079.
Анотація:
Cette thèse concerne trois problèmes de réalisations géométriques de structures combinatoires par des polytopes et des subdivisions polyédrales. Un polytope est l'enveloppe convexe d'un ensemble fini de points dans un espace euclidien R^d. Il est muni d'une structure combinatoire donnée par ses faces. Une subdivision est une collection de polytopes dont les faces s'intersectent correctement et dont l'union est convexe. Elle est régulière si elle peut être obtenue en prenant les faces inférieures d'un relèvement de ses sommets dans une dimension de plus.Nous présentons d'abord une nouvelle construction géométrique d'un grand nombre de polytopes combinatoirement distincts, de dimension et nombre de sommets fixés. Cette construction consiste à montrer que certains polytopes admettent un grand nombre de triangulations régulières. Elle nous permet d'améliorer la meilleure borne inférieure connue sur le nombre de types combinatoires de polytopes.Nous étudions ensuite les projections du permutoèdre, nommées polytopes de balayage (sweep polytopes) parce qu'elles modélisent les manières d'ordonner une configuration de points fixée en balayant l'espace par des hyperplans dans une direction constante. Nous introduisons également et étudions une abstraction combinatoire de ces structures : les matroïdes orientés de balayage, qui généralisent en dimension supérieure à 2 la théorie des suites admissibles de Goodman et Pollack.Enfin, nous proposons des réalisations géométriques de l'ordre s-faible, une structure combinatoire qui généralise l'ordre faible sur les permutations, paramétrée par un vecteur s à coordonnées entières strictement positives. En particulier, nous résolvons une conjecture de Ceballos et Pons en montrant que le s-permutoèdre peut être réalisé comme le graphe d'un complexe polytopal qui est une subdivision du permutoèdreThis thesis concerns three problems of geometric realizations of combinatorial structures via polytopes and polyhedral subdivisions. A polytope is the convex hull of a finite set of points in a Euclidean space R^d. It is endowed with a combinatorial structure coming from its faces. A subdivision is a collection of polytopes whose faces intersect properly and such that their union is convex. It is regular if it can be obtained by taking the lower faces of a lifting of its vertices in one dimension higher.We first present a new geometric construction of many combinatorially different polytopes of fixed dimension and number of vertices. This construction relies on showing that certain polytopes admit many regular triangulations. It allows us to improve the best known lower bound on the number of combinatorial types of polytopes.We then study the projections of permutahedra, that we call sweep polytopes because they model the possible orderings of a fixed point configuration by hyperplanes that sweep the space in a constant direction. We also introduce and study a combinatorial abstraction of these structures: the sweep oriented matroids, that generalize Goodman and Pollack's theory of allowable sequences to dimensions higher than 2.Finally, we provide geometric realizations of the s-weak order, a combinatorial structure that generalizes the weak order on permutations, parameterized by a vector s with positive integer coordinates. In particular, we answer Ceballos and Pons conjecture that the s-weak order can be realized as the edge-graph of a polytopal complex that is moreover a subdivision of a permutahedron
6
Diakité, Abdoulaye Abou. "Application des cartes combinatoires à la modélisation géométrique et sémantique des bâtiments." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10281/document.
Анотація:
Les modèles 3D de bâtiment sont largement utilisés dans l'industrie de la construction et sont nécessités par plusieurs applications telles que la représentation architecturale et les processus de simulation. Malheureusement, ces modèles manquent souvent d'informations d'une importance majeure pour permettre d'effectuer des opérations d'analyse et de calcul. Les modèles originaux sont alors souvent reconstruits par les différents acteurs qui les utilisent afin de les rendre plus adaptés à leur besoins. Dans le but de pallier ce problème, nous introduisons une approche permettant d'enrichir un modèle 3D de bâtiment et le rendre beaucoup plus interopérable. À partir de l'information géométrique seulement, nous rajoutons au modèle des informations topologiques et sémantiques. Une subdivision cellulaire de l'espace occupé par le bâtiment est d'abord effectuée en se basant sur sa géométrie, puis les relations topologiques entre les cellules sont reconstruites et explicitement définies. Des étiquettes sémantiques sont ensuite attribuées aux composants identifiés du bâtiment à l'aide de la topologie reconstruite et des règles heuristiques prédéfinies. Une structure de données topologique appelée carte combinatoire 3D (3-carte) est utilisée comme une base solide pour la mise au point des opération de reconstruction et le traitement des informations reconstruites. À partir du modèle enrichi, nous montrons comment extraire des données pour des applications dédiées, par exemple la simulation acoustique et lancer de rayon pour la navigation intérieure. Notre méthode se présente comme un pont entre les approches de modélisation et les applications d'analyse du bâtiment qui utilisent ces modèles. Il est entièrement automatique et présente des résultats intéressants sur plusieurs types de modèles3D building models are widely used in the civil engineering industry. While the models are needed by several applications, such as architectural representations and simulation processes, they often lack of information that are of major importance for the consistency of the calculations. The original models are then often rebuilt in the way that fits better to the intended applications. To overcome this drawback, we introduce a framework allowing to enrich a 3D model of a building presenting just a geometry, in a way more interoperable model, by adding to it topological and semantic information. A cellular subdivision of the building space is first performed relying on its geometry, then the topological relationships between the cells are explicitely defined. Semantic labels are then attributed to the identified components based on the topology and defined heuristic rules. A 3D combinatorial map data structure (3-map) is used to handle the reconstructed information. From the enriched model we show how to extract applications-driven information allowing to perform acoustic simulation and indoor ray tracing navigation. The approach stands as a bridge between the modeling approaches and the applications in building analysis using the model. It is fully automatic and present interesting results on several types of building models
7
Pacheco-Martínez, Ana María. "Extracting cell complexes from 4-dimensional digital images." Thesis, Poitiers, 2012. http://www.theses.fr/2012POIT2262/document.
Анотація:
Une image numérique peut être définie comme un ensemble de n-xels sur une grille constituée de n-cubes. La segmentation consiste à calculer une partition d'une image en régions. Les n-xels ayant des caractéristiques similaires (couleur, intensité, etc.) sont regroupés. Schématiquement, à chaque n-xel est attribuée une étiquette, et chaque région de l'image est constituée de n-xels de même étiquette. Les méthodes "de type" Marching cubes et Kenmochi et al. construisent des complexes représentant la topologie de la région d'intérêt d'une image numérique binaire de dimension 3. Dans la première méthode, l'algorithme construit un complexe simplicial, dont 0-cellules sont des points des arêtes de la grille duale. Dans la deuxième méthode, les auteurs construisent un complexe cellulaire sur une grille duale, c.a.d les 0-cellules du complexe sont des sommets de la grille duale. Afin de construire le complexe, Kenmochi et al. calculent (à rotations près) les différentes configurations de sommets blancs et noirs d'un cube, puis, ils construisent les enveloppes convexes des points noirs de ces configurations. Ces enveloppes convexes définissent les cellules du complexe, à rotations près. Le travail développé dans cette thèse étend la méthode de Kenmochi et al. en dimension 4. L'objectif est de construire un complexe cellulaire à partir d'une image numérique binaire définie sur une grille duale. Nous calculons d'abord les différentes configurations de sommets blancs et noirs d'un 4-cube (à isométries près), puis, nous construisons des enveloppes convexes définies par ces configurations. Ces enveloppes convexes sont construites par déformation du 4-cube d'origine, et nous distinguonA digital image can be defined as a set of n-xels on a grid made up by n-cubes. Segmentation consists in computing a partition of an image into regions. The n-xels having similar characteristics (color, intensity, etc.) are regrouped. Schematically, each n-xel is assigned a label, and each region of the image is made up by n-xels with the same label. The methods "type" Marching cubes and Kenmochi et al. construct complexes representing the topology of the region of interest of a 3-dimensional binary digital image. In the first method, the algorithm constructs a simplicial complex, whose 0-cells are points of the edges of the dual grid. Inthe second one, the authors construct a cell complex on a dual grid, i.e. the 0-cells of the complex are vertices of the dual grid. In order to construct the complex, Kenmochi et al. compute (up to rotations) the different configurations of white and black vertices of a cube, and then, they construct the convex hulls of the black points of these configurations. These convex hulls define the cells of the complex, up to rotations. The work developed in this thesis extends Kenmochi et al. method todimension 4. The goal is to construct a cell complex from a binary digital image defined on a dual grid. First, we compute the different configurations of white and black vertices of a 4-cube, up to isometries, and then, we construct the convex hulls defined by these configurations. These convex hulls are constructed by deforming the original 4-cube, and we distinguishseveral basic construction operations (deformation, degeneracy of cells, etc.). Finally, we construct the cell complex corresponding to the dual image by assembling the cells so o
Una imagen digital puede ser definida como un conjunto de n–xeles en un mallado constituido de n–cubos. Los n–xeles pueden ser identificados con: (1) los n–cubos del mallado, o con (2) los puntos centrales de estos n–cubos. En el primer caso, trabajamos con un mallado primal, mientras que en el segundo, trabajamos con un mallado dual construido a partir del mallado primal. La segmentación consiste en calcular una partición de una imagen en regiones. Los n–xeles que tienen características similares (color, intensidad, etc.) son reagrupados. Esquemáticamente, a cada n–xel se le asocia una etiqueta, y cada región de la imagen está constituida de n–xeles con la misma etiqueta. En particular, si las únicas etiquetas permitidas para los n–xeles son “blanca” y “negra”, la segmentación se dice binaria: los n–xeles negros forman el primer plano (foreground) o región de interés en cuestión de análisis de la imagen, y los n–xeles blancos forman el fondo (background). Ciertos modelos, como los Grafos de Adyacencia de Regiones (RAGs), los Grafos Duales (DGs) y la carta topológica, han sido propuestos para representar las particiones en regiones, y en particular para representar la topología de estas regiones, es decir las relaciones de incidencia y/o adyacencia entre las diferentes regiones. El RAG [27] es un precursor de este tipo de modelos, y ha sido una fuente de inspiración de los DGs [18] y de la carta topológica [9, 10]. Un RAG representa una imagen primal etiquetada por un grafo: los vértices del grafo corresponden a regiones de la imagen, y las aristas del grafo representan las relaciones de adyacencia entre la regiones. Los DGs son un modelo que permite resolver ciertos inconvenientes de los RAGs para representar imágenes de dimensión 2. La carta topológica es una extensión de los modelos anteriores definida para manipular imágenes primales de dimensión 2 y 3, representando no solamente las relaciones topológicas, sino también las relaciones geométricas
8
Dovgal, Sergey. "An interdisciplinary image of Analytic Combinatorics." Thesis, Paris 13, 2019. http://www.theses.fr/2019PA131065.
Анотація:
Cette thèse est consacrée au développement des outils et à l’utilisation des méthodes de la combinatoire analytique, notamment l’énumération exacte et asymptotique, les propriétés statistiques des objets aléatoires et la génération aléatoire. L’ingrédient clé est la multidisciplinarité du domaine, qui est soulignée par des exemples tirés de la programmation logique, de la mécanique statistique, de la biologie, de la statistique mathématique, des réseaux et de la théorie des files d’attenteThis thesis is devoted to the development of tools and the use of methods from Analytic Combinatorics, including exact and asymptotic enumeration, statistical properties of random objects, and random generation.The key ingredient is the multidisciplinarity of the domain, which is emphasised by using examples from computational logic, statistical mechanics, biology, mathematical statistics, networks and queueing theory
9
Janaqi, Stefan. "Quelques éléments de la géométrie des graphes : graphes médians, produits d'arbres, génération convexe des graphes de Polymino." Université Joseph Fourier (Grenoble), 1994. http://www.theses.fr/1995GRE10093.
Анотація:
La notion d'intervalle dans un graphe, traduit de façon naturelle la notion du segment dans les espaces euclidiens. Par analogie, un ensemble C de sommets est convexe si pour tout couple x, y de sommets de C, l'intervalle entre x et y est inclu dans C. En utilisant la convexité géodésique, Djokovic a caractérisé les graphes isométriquement plongeable dans l'hypercube. Une vingtaine d'années plus tard, Mulder a caractérisé les graphes médians comme des graphes isométriquement plongeable dans l'hypercube et qui sont fermés pour l'opération médian. La comprehension du lien apparent entre ces deux résultats, nous a permis de trouver une nouvelle caractérisation, d'inspiration géométrique, des graphes médians. Cette caractérisation nous a permis à reconnaître les graphes médians qui sont des produits d'arbres ou de chemins. Nous avons donné une caractérisation de ces produits par mineurs convexes exclus. Un autre groupe de résultats concerne des graphes définis naturellement à partir des polyminos. En cherchant le nombre minimum de sommets qui engendrent convexement un tel graphe G, nous avons trouvé que ce nombre est égal au nombre maximum de sommets de degré un d'un arbre obtenu à partir de G par la contraction d'arêtes bien choisies
10
Jacques, Isabelle. "Aspects combinatoires en modélisation 2D et 3D et application à l'énumération des cartes et des solides." Mulhouse, 1991. http://www.theses.fr/1991MULH0185.
Анотація:
Après les travaux de W. T. Tutte sur le comptage de diverses familles de cartes planaires, le point de vue adopté ici est celui de la définition de transformations topologiques sur les cartes à partir desquelles on déduit des équations sur leurs séries génératrices. Un premier résultat concerne l'énumération des cartes sur le tore en fonction du nombre d'arêtes et du degré d'une face distinguée. Une nouvelle équation sur la série génératrice est obtenue après une étude détaillée d'une transformation topologique consistant à contracter une face distinguée. Un second résultat concerne l'étude d'un problème d'évolution linéaire sur un multigraphe muni d'une valuation formelle. La résolution de ce problème conduit à une équation nouvelle attachée à tout graphe. Cette équation, appliquée dans le cas particulier de l'arbre infini naturellement associé à la famille des cartes planaires, conduit à une équation nouvelle pour la série génératrice de ces cartes planaires, exprimant celle-ci en fonction de la série génératrice des mots de Dyck. Le troisième résultat concerne une généralisation à trois dimensions au niveau des solides topologiques, des notions classiques sur les cartes. La notion de solide est introduite en termes de sommets, arêtes, faces et en y ajoutant une composante supplémentaire : celle de volume. Une propriété importante mise en évidence est celle d'effeuillabilité, celle-ci permettant de généraliser en 3D la notion d'arbre par celle de solide effeuillable. On donne alors l'énumération d'une classe particulière de tels solides effeuillables : les solides-arbres par la suite de Schröder-Etherington
Книги з теми "Combinatoire géométrique":
1
Grötschel, Martin. Geometric algorithms and combinatorial optimization. 2nd ed. Berlin: Springer-Verlag, 1993.
2
Grötschel, Martin. Geometric algorithms and combinatorial optimization. Berlin: Springer-Verlag, 1988.
3
Orlik, Peter. Introduction to arrangements. Providence, R.I: Published for the Conference Board of the Mathematical Sciences by the American Mathematical Society, 1989.
4
Deledicq, André. Le monde des pavages. 2nd ed. [Paris]: ACL-Éditions du Kangourou, 1997.
5
E, Goodman Jacob, and O'Rourke Joseph, eds. Handbook of discrete and computational geometry. 2nd ed. Boca Raton: Chapman & Hall/CRC, 2004.
6
Pach, Janos. Thirty Essays on Geometric Graph Theory. New York, NY: Springer New York, 2013.
7
Agarwal, Pankaj K. Intersection and decomposition algorithms for planar arrangements. Cambridge: Cambridge University Press, 1991.
8
Kisačanin, Branislav. Mathematical problems and proofs: Combinatorics, number theory, and geometry. New York: Plenum Press, 1998.
9
Kisačanin, Branislav. Mathematical Problems and Proofs: Combinatorics, Number Theory, and Geometry. Cleveland: Kluwer Academic Publishers, 2002.
10
JCDCG 2004 (2004 Tokyo, Japan). Discrete and computational geometry: Japanese conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004 : revised selected papers. Berlin: Springer, 2005.
Частини книг з теми "Combinatoire géométrique":
1
"Géométrie et combinatoire." In CRM Monograph Series, 1. Providence, Rhode Island: American Mathematical Society, 2013. http://dx.doi.org/10.1090/crmm/031/01.