To see the other types of publications on this topic, follow the link: Simplicial complexes and polytopes.
Dissertations / Theses on the topic 'Simplicial complexes and polytopes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Simplicial complexes and polytopes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Cartier, Noémie. "Lattice properties of acyclic pipe dreams." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG065.
Full textAbstract:
Cette thèse s'inscrit dans le domaine de la combinatoire algébrique. Certains algorithmes de tri peuvent être décrits par des diagrammes appelés réseaux de tri, et l'exécution de ces algorithmes sur des permutations se traduit alors par des arrangements de courbes sur ces réseaux. Ces arrangements donnent des modèles pour des structures combinatoires classiques : par exemple, le treillis de Tamari, dont les relations de couverture sont les rotations sur les arbres binaires, et qui est un quotient bien connu de l'ordre faible sur les permutations. Les complexes de sous-mots généralisent les réseaux de tris et les arrangements de courbes aux groupes de Coxeter. Ils ont des liens profonds en algèbre et géométrie, notamment dans le calcul de Schubert, l'étude des variétés grassmanniennes et la théorie des algèbres amassées. Cette thèse s'intéresse aux structures de treillis sur certains complexes de sous-mots, généralisant les treillis de Tamari. Plus précisément, elle étudie la relation définie par les extensions linéaires des facettes d'un complexe de sous-mot. Dans un premier lieu, nous nous intéressons aux complexes de sous-mots définis sur un mot triangulaire du groupe symétrique, que nous représentons par des arrangements de tuyaux triangulaires. Nous prouvons alors que cette relation définit un quotient de treillis d'un intervalle de l'ordre faible ; par ailleurs, nous pouvons également utiliser cette relation pour définir un morphisme de treillis de cet intervalle au graphe des flips du complexe de sous-mots restreint à certaines de ses facettes. Dans un second lieu, nous étendons notre étude aux complexes de sous-mots définis sur les mots alternants du groupe symétrique. Nous montrons que cette même relation définit également un quotient de treillis ; en revanche, le morphisme associé n'a plus pour image le graphe des flips, mais le squelette du polyhèdre de brique, un objet défini sur les complexes de sous-mots pour étudier des réalisations du multi-associahèdre. Enfin, nous discutons des possibles extensions de ces résultats aux groupes de Coxeter finis, ainsi que de leurs applications pour généraliser certains objets définis en type A comme les treillis de nu-TamariThis thesis comes within the scope of algebraic combinatorics. Some sorting algorithms can be described by diagrams called sorting networks, and the execution of the algorithms on input permutations translates to arrangements of curves on the networks. These arrangements modelize some classical combinatorial structures: for example, the Tamari lattice, whose cover relations are the rotations on binary trees, and which is a well-known quotient of the weak order on permutations. Subword complexes generalize sorting network and arrangements of curves to Coxeter groups. They have deep connections in algebra and geometry, in particular in Schubert calculus, in the study of grassmannian varieties, and in the theory of cluster algebras. This thesis focuses on lattice structures on some subword complexes, generalizing Tamari lattices. More precisely, it studies the relation defined by linear extensions of the facets of a subword complex. At first we focus on subword complexes defined on a triangular word of the symmetric group, which we represent with triangular pipe dreams. We prove that this relation defines a lattice quotient of a weak order interval; moreover, we can also use this relation to define a lattice morphism from this interval to the restriction of the flip graph of the subword complex to some of its facets. Secondly, we extent our study to subword complexes defined on alternating words of the symmetric group. We prove that this same relation also defines a lattice quotient; however, the image of the associated morphism is no longer the flip graph, but the skeleton of the brick polyhedron, an object defines on subword complexes to study realizations of the multiassociahedron. Finally, we discuss possible extensions of these results to finite Coxeter groups, as well as their applications to generalize some objects defined in type A such as nu-Tamari lattices
2
Jonsson, Jakob. "Simplicial Complexes of Graphs." Doctoral thesis, Stockholm, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-202.
Full text
3
Jonsson, Jakob. "Simplicial complexes of graphs /." Berlin [u.a.] : Springer, 2008. http://dx.doi.org/10.1007/978-3-540-75858-7.
Full text
4
Mirmohades, Djalal. "Simplicial Structure on Complexes." Licentiate thesis, Uppsala universitet, Algebra och geometri, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-221410.
Full text
5
Zhang, Zhihan. "Random walk on simplicial complexes." Electronic Thesis or Diss., université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM010.
Full textAbstract:
La notion de laplacien d’un graphe peut être généralisée aux complexes simpliciaux et aux hypergraphes. Cette notion contient des informations sur la topologie de ces structures. Dans la première partie de cette thèse,nous définissons une nouvelle chaîne de Markov sur les complexes simpliciaux. Pour un degré donné k de simplexes, l’espace d’états n’est pas les k-simplexes comme dans les articles précédents sur ce sujet mais plutôt l’ensemble des k-chaines ou k-co-chaines. Ce nouveau cadre est la généralisation naturelle sur les chaînes de Markov canoniques sur des graphes. Nous montrons que le générateur de notre chaîne de Markov est lié au Laplacien supérieur défini dans le contexte de la topologie algébrique pour structure discrète. Nous établissons plusieurs propriétés clés de ce nouveau procédé. Nous montrons que lorsque les complexes simpliciaux examinés sont une séquence de triangulation du tore plat, les chaînes de Markov tendent vers une forme différentielle valorisée processus continu.Dans la deuxième partie de cette thèse, nous explorons quelques applications de la marche aléatoire, i.e. la détection de trous basée sur la marche aléatoire et les noyaux complexes simpliciaux. Pour la détection de trous basée sur la marche aléatoire, nous introduisons un algorithme pour faire des simulations effectuées pour la marche aléatoire à valeur cyclique (k = 1) sur un complexe simplicial avec trous. Pour les noyaux de complexes simpliciaux, nous étendons la définition des noyaux de graphes basés sur la marche aléatoire afin de mesurer la similitude entre deux complexes simpliciauxThe notion of Laplacian of a graph can be generalized to simplicial complexes and hypergraphs. This notion contains information on the topology of these structures. In the first part of this thesis, we define a new Markov chain on simplicial complexes. For a given degree k of simplices, the state space is not thek-simplices as in previous papers about this subject but rather the set of k-chains or k-cochains.This new framework is the natural generalization on the canonical Markov chains on graphs.We show that the generator of our Markov chainis related to the upper Laplacian defined in the context of algebraic topology for discrete structure. We establish several key properties of this new process. We show that when the simplicial complexes under scrutiny are a sequence of ever refining triangulation of the flat torus, the Markov chains tend to a differential form valued continuous process.In the second part of this thesis, we explore some applications of the random walk, i.e., random walk based hole detection and simplicial complexes kernels. For the random walk based hole detection, we introduce an algorithm tomake simulations carried for the cycle-valuedrandom walk (k = 1) on a simplicial complex with holes. For the simplicial complexes kernels,we extend the definition of random walk based graph kernels in order to measure the similarity between two simplicial complexes
6
Zuffi, Lorenzo. "Simplicial Complexes From Graphs Toward Graph Persistence." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/13519/.
Full textAbstract:
Persistent homology is a branch of computational topology which uses geometry and topology for shape description and analysis. This dissertation is an introductory study to link persistent homology and graph theory, the connection being represented by various methods to build simplicial complexes from a graph. The methods we consider are the complex of cliques, of independent sets, of neighbours, of enclaveless sets and complexes from acyclic subgraphs, each revealing several properties of the underlying graph. Moreover, we apply the core ideas of persistence theory in the new context of graph theory, we define the persistent block number and the persistent edge-block number.
7
Petersson, Anna. "Enumeration of spanning trees in simplicial complexes." Licentiate thesis, Uppsala universitet, Matematiska institutionen, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-138976.
Full text
8
Egan, Sarah. "Nash equilibria in games and simplicial complexes." Thesis, University of Bath, 2008. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.500758.
Full textAbstract:
Nash's Theorem is a famous and widely used result in non-cooperative game theory which can be applied to games where each player's mixed strategy payoff function is defined as an expectation. Current proofs of this Theorem neither justify why this constraint is necessary or satisfactorily identifies its origins. In this Thesis we change this and prove Nash's Theorem for abstract games where, in particular, the payoff functions can be replaced by total orders. The result of this is a combinatoric proof of Nash's Theorem. We also construct a generalised simplicial complex model and demonstrate a more general form of Nash's Theorem holds in this setting. This leads to the realisation Nash's Theorem is not a consequence of a fixed-point theorem but rather a combinatoric phenomenon existing in a much more general mathematical model.
9
Hetyei, Gábor. "Simplicial and cubical complexes : anologies and differences." Thesis, Massachusetts Institute of Technology, 1994. http://hdl.handle.net/1721.1/32610.
Full text
10
Perkins, Simon. "Field D* pathfinding in weighted simplicial complexes." Doctoral thesis, University of Cape Town, 2013. http://hdl.handle.net/11427/6433.
Full textAbstract:
Includes abstract.Includes bibliographical references.
The development of algorithms to efficiently determine an optimal path through a complex environment is a continuing area of research within Computer Science. When such environments can be represented as a graph, established graph search algorithms, such as Dijkstra’s shortest path and A*, can be used. However, many environments are constructed from a set of regions that do not conform to a discrete graph. The Weighted Region Problem was proposed to address the problem of finding the shortest path through a set of such regions, weighted with values representing the cost of traversing the region. Robust solutions to this problem are computationally expensive since finding shortest paths across a region requires expensive minimisation. Sampling approaches construct graphs by introducing extra points on region edges and connecting them with edges criss-crossing the region. Dijkstra or A* are then applied to compute shortest paths. The connectivity of these graphs is high and such techniques are thus not particularly well suited to environments where the weights and representation frequently change. The Field D* algorithm, by contrast, computes the shortest path across a grid of weighted square cells and has replanning capabilites that cater for environmental changes. However, representing an environment as a weighted grid (an image) is not space-efficient since high resolution is required to produce accurate paths through areas containing features sensitive to noise. In this work, we extend Field D* to weighted simplicial complexes – specifically – triangulations in 2D and tetrahedral meshes in 3D.
11
Newman, J. Andrew. "Torsion in Homology of Random Simplicial Complexes." The Ohio State University, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=osu1531499208297615.
Full text
12
Kahle, Matthew. "Topology of random simplicial complexes and phase transitions for homology /." Thesis, Connect to this title online; UW restricted, 2007. http://hdl.handle.net/1773/5809.
Full text
13
Zagrodny, Christopher Michael. "Algebraic Concepts in the Study of Graphs and Simplicial Complexes." Digital Archive @ GSU, 2006. http://digitalarchive.gsu.edu/math_theses/7.
Full textAbstract:
This paper presents a survey of concepts in commutative algebra that have applications to topology and graph theory. The primary algebraic focus will be on Stanley-Reisner rings, classes of polynomial rings that can describe simplicial complexes. Stanley-Reisner rings are defined via square-free monomial ideals. The paper will present many aspects of the theory of these ideals and discuss how they relate to important constructions in commutative algebra, such as finite generation of ideals, graded rings and modules, localization and associated primes, primary decomposition of ideals and Hilbert series. In particular, the primary decomposition and Hilbert series for certain types of monomial ideals will be analyzed through explicit examples of simplicial complexes and graphs.
14
Zhu, Xueyun. "Vlist and Ering: compact data structures for simplicial 2-complexes." Thesis, Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/50389.
Full textAbstract:
Various data structures have been proposed for representing the connectivity of manifold triangle meshes. For example, the Extended Corner Table (ECT) stores V+6T references, where V and T respectively denote the vertex and triangle counts. ECT supports Random Access and Traversal (RAT) operators at Constant Amortized Time (CAT) cost. We propose two novel variations of ECT that also support RAT operations at CAT cost, but can be used to represent and process Simplicial 2-Complexes (S2Cs), which may represent star-connecting, non-orientable, and non-manifold triangulations along with dangling edges, which we call sticks. Vlist stores V+3T+3S+3(C+S-N) references, where S denotes the stick count, C denotes the number of edge-connected components and N denotes the number of star-connecting vertices. Ering stores 6T+3S+3(C+S-N) references, but has two advantages over Vlist: the Ering implementation of the operators is faster and is purely topological (i.e., it does not perform geometric queries). Vlist and Ering representations have two principal advantages over previously proposed representations for simplicial complexes: (1) Lower storage cost, at least for meshes with significantly more triangles than sticks, and (2) explicit support of side-respecting traversal operators which each walks from a corner on the face of a triangle t across an edge or a vertex of t, to a corner on a faces of a triangle or to an end of a stick that share a vertex with t, and this without ever piercing through the surface of a triangle.
15
Abramchuk, Yauheniya [Verfasser], and Volker [Gutachter] Kaibel. "Undominated complexes of cut polytopes / Yauheniya Abramchuk ; Gutachter: Volker Kaibel." Magdeburg : Universitätsbibliothek Otto-von-Guericke-Universität, 2018. http://d-nb.info/121996543X/34.
Full text
16
Muhammad, Abubakr. "Graphs, Simplicial Complexes and Beyond: Topological Tools for Multi-agent Coordination." Diss., Available online, Georgia Institute of Technology, 2005, 2005. http://etd.gatech.edu/theses/available/etd-11152005-171405/.
Full textAbstract:
Thesis (Ph. D.)--Electrical and Computer Engineering, Georgia Institute of Technology, 2006.Symington, Margaret, Committee Member ; Howard, Ayanna, Committee Member ; Tannenbaum, Allen, Committee Member ; Verriest, Erik, Committee Member ; Egerstedt, Magnus, Committee Chair. Vita. Includes bibliographical references.
17
Weigel, Christian Jens [Verfasser]. "Gated chamber complexes, simplicial arrangements and Coxeter groups / Christian Jens Weigel." Gießen : Universitätsbibliothek, 2015. http://d-nb.info/1075144884/34.
Full text
18
Rauße, Christian [Verfasser], and Christoph [Akademischer Betreuer] Böhm. "Simplicial complexes of compact homogeneous spaces / Christian Rauße ; Betreuer: Christoph Böhm." Münster : Universitäts- und Landesbibliothek Münster, 2017. http://d-nb.info/1142528421/34.
Full text
19
Chebbi, Yassin. "Laplacien discret d'un 2-complexe simplicial." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4028/document.
Full text
20
Salve, Dias Fabio Augusto. "A study of some morphological operators in simplicial complex spaces." Phd thesis, Université Paris-Est, 2012. http://pastel.archives-ouvertes.fr/pastel-00824751.
Full textAbstract:
In this work we study the framework of mathematical morphology on simplicial complex spaces. Simplicial complexes are a versatile and widely used structure to represent multidimensional data, such as meshes, that are tridimensional complexes, or graphs, that can be interpreted as bidimensional complexes. Mathematical morphology is one of the most powerful frameworks for image processing, including the processing of digital structures, and is heavily used for many applications. However, mathematical morphology operators on simplicial complex spaces is not a concept fully developped in the literature. In this work, we review some classical operators from simplicial complexes under the light of mathematical morphology, to show that they are morphology operators. We define some basic lattices and operators acting on these lattices: dilations, erosions, openings, closings and alternating sequential filters, including their extension to weighted simplexes. However, the main contributions of this work are what we called dimensional operators, small, versatile operators that can be used to define new operators on simplicial complexes, while mantaining properties from mathematical morphology. These operators can also be used to express virtually any operator from the literature. We illustrate all the defined operators and compare the alternating sequential filters against filters defined in the literature, where our filters show better results for removal of small, intense, noise from binary images
21
Adams-Florou, Spiros. "Homeomorphisms, homotopy equivalences and chain complexes." Thesis, University of Edinburgh, 2012. http://hdl.handle.net/1842/6250.
Full textAbstract:
This thesis concerns the relationship between bounded and controlled topology and in particular how these can be used to recognise which homotopy equivalences of reasonable topological spaces are homotopic to homeomorphisms. Let f : X → Y be a simplicial map of finite-dimensional locally finite simplicial complexes. Our first result is that f has contractible point inverses if and only if it is an ε- controlled homotopy equivalences for all ε > 0, if and only if f × id : X × R → Y × R is a homotopy equivalence bounded over the open cone O(Y +) of Pedersen and Weibel. The most difficult part, the passage from contractible point inverses to bounded over O(Y +) is proven using a new construction for a finite dimensional locally finite simplicial complex X, which we call the fundamental ε-subdivision cellulation X'ε. This whole approach can be generalised to algebra using geometric categories. In the second part of the thesis we again work over a finite-dimensional locally finite simplicial complex X, and use the X-controlled categories A*(X), A*(X) of Ranicki and Weiss (1990) together with the bounded categories CM(A) of Pedersen and Weibel (1989). Analogous to the barycentric subdivision of a simplicial complex, we define the algebraic barycentric subdivision of a chain complex over that simplicial complex. The main theorem of the thesis is then that a chain complex C is chain contractible in ( A*(X) A*(X) if and only if “C ¤ Z” 2 (A*(X × R) A*(X × R) is boundedly chain contractible when measured in O(X+) for a functor “ − Z” defined appropriately using algebraic subdivision. In the process we prove a squeezing result: a chain complex with a sufficiently small chain contraction has arbitrarily small chain contractions. The last part of the thesis draws some consequences for recognising homology manifolds in the homotopy types of Poincare Duality spaces. Squeezing tells us that a PL Poincare duality space with sufficiently controlled Poincare duality is necessarily a homology manifold and the main theorem tells us that a PL Poincare duality space X is a homology manifold if and only if X × R has bounded Poincare duality when measured in the open cone O(X+).
22
Du, Dong. "Contributions to Persistence Theory." The Ohio State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=osu1338304358.
Full text
23
Ellis, Robert B. "A Kruskal-Katona theorem for cubical complexes." Thesis, Virginia Tech, 1996. http://hdl.handle.net/10919/45075.
Full textAbstract:
The optimal number of faces in cubical complexes which lie in cubes refers to the
maximum number of faces that can be constructed from a certain number of faces of
lower dimension, or the minimum number of faces necessary to construct a certain
number of faces of higher dimension. If m is the number of faces of r in a
cubical complex, and if s > r(s < r), then the maximum(minimum) number of faces
of dimension s that the complex can have is
m(s/r) +. (m-m(r/r))(s/r), in terms of
upper and lower semipowers. The corresponding formula for simplicial complexes,
proved independently by J. B. Kruskal and G. A. Katona, is m(s/r). A proof of
the formula for cubical complexes is given in this paper, of which a flawed version
appears in a paper by Bernt Lindstrijm. The n-tuples which satisfy the optimaiity
conditions for cubical complexes which lie in cubes correspond bijectively with f-vectors
of cubical complexes.
Master of Science
24
Nisse, Mounir. "Sur la géométrie et la topologie des amibes et coamibes des variétés algébriques complexes." Paris 6, 2010. http://www.theses.fr/2010PA066131.
Full textAbstract:
Un des nouveaux domaine de mathématiques pures appelé “géométrie tropicale” a vu un développement spectaculaire au cours de ces derniéres années. En géométrie énumérative, récemment Gregory Mikhalkin a donné une interprétation des invariants de Gromov-Witten en termes de géométrie tropicale en comptant des chemins entiers dans des polytopes entiers (Théorème de correspondance de Mikhalkin \cite{M2-04}). En utilisant des outils analogues, Andreas Gathmann et Hannah Markwig redécouvrent la formule de Caporaso-Harris pour les courbes complexes planes ainsi que les formules de Kontsevich pour les courbes rationnelles complexes et planes en termes de géométrie tropicale. Cette géométrie est liée à la géométrie algébrique classique par des objets géométriques appelés amibes et coamibes. La première terminologie, qui est la notion clef de la géométrie tropicale, est introduite pour la premiére fois en mathématiques par I. M. Gelfand, M. M. Kapranov et A. V. Zelevinsky en 1994. La seconde terminologie est introduite par M. Passare et A. Tsikh en 2000 dans plusieurs de leurs exposés un peu partout dans le monde. Ces formes de vie unicellulaires sont étudiées et bien connues en biologie. L'amibe plane est un objet géométrique qui fait allusion à une région ayant plusieurs trous (vocuolos) et des tentacules droites et pointues (pseudopodes). Ces tentacules atteignent l'infini et chacune d'elles se contracte exponentiellement vers un rayon (son squelette; voir la courte Note de Oleg Viro dans les Notes de l'AMS en 2002 pour une bref introduction sur les amibes). L'idée est de réduire à zéro l'épaisseur de ces amibes (bien sûr en essayant de garder le maximum d'informations géométriques , topologiques et autres propriétés de l'objet initial) et ainsi obtenir un objet tropical i. E. , purement combinatoire. Ce qui veut dire que les variétés tropicales apparaissent comme une certaine dégénérescence de ces objets. L'amibe d'une variété algébrique complexe dans l’espace complexe de dimension n est son image dans l’espace reel de dimension n par l'application logarithmique, c'est donc un objet qui vit dans l'espace réel, mais qui illustre de nombreuses caractéristiques de la variété complexe. On s'interesse dans cette these à la géométrie ainsi que la topologie de ces deux objets. On démontre plusieurs nouveaux réesultats concernant les coamibes, géométriques topologiques et combinatoires. On montre aussi leurs liens avec le polytope de Newton dans le cas des hypersurfaces, ainsi que leur similarités.
25
Zeckner, Matthew. "TOPOLOGICAL AND COMBINATORIAL PROPERTIES OF NEIGHBORHOOD AND CHESSBOARD COMPLEXES." UKnowledge, 2011. http://uknowledge.uky.edu/gradschool_diss/163.
Full textAbstract:
This dissertation examines the topological properties of simplicial complexes that arise from two distinct combinatorial objects. In 2003, A. Björner and M. de Longueville proved that the neighborhood complex of the stable Kneser graph SGn,k is homotopy equivalent to a k-sphere. Further, for n = 2 they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron. They went on to ask whether or not, for all n and k, the neighborhood complex of SGn,k contains as a deformation retract the boundary complex of a simplicial polytope. Part one of this dissertation provides a positive answer to this question in the case k = 2. In this case it is also shown that, after partially subdividing the neighborhood complex, the resulting complex deformation retracts onto a subcomplex arising as a polyhedral boundary sphere that is invariant under the action induced by the automorphism group of SGn,2. Part two of this dissertation studies simplicial complexes that arise from non-attacking rook placements on a subclass of Ferrers boards that have ai rows of length i where ai > 0 and i ≤ n for some positive integer n. In particular, enumerative properties of their facets, homotopy type, and homology are investigated.
26
Tambour, Jérôme. "Complexes moment-angle et variétés complexes." Phd thesis, Université de Bourgogne, 2010. http://tel.archives-ouvertes.fr/tel-00648247.
Full textAbstract:
Le but de cette thèse est d'étendre les résultats de l'article [B-M] sur les relations entre variétés moment-angle et variétés complexes. On s'intéressera ici aux variétés moment-angle issues d'une décomposition simpliciale (et non simplement polytopale) de la sphère. On cherchera ensuite à utiliser la relation entre ces deux types d'objets pour comprendre la topologie de certaines variétés complexes.[B-M] F.Bosio, L.Meersseman, Real quadrics in Cn, complex manifolds and polytopes, Acta Mathematica, 197 (2006), n° 1, 53 -- 127.
27
Knöppel, Felix Jakob [Verfasser], Ulrich [Akademischer Betreuer] Pinkall, Ulrich [Gutachter] Pinkall, Boris [Gutachter] Springborn, and Johannes [Gutachter] Wallner. "Complex line bundles over simplicial complexes / Felix Jakob Knöppel ; Gutachter: Ulrich Pinkall, Boris Springborn, Johannes Wallner ; Betreuer: Ulrich Pinkall." Berlin : Technische Universität Berlin, 2016. http://d-nb.info/1156013682/34.
Full text
28
Kowalick, Ryan. "Discrete Systolic Inequalities." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1384873457.
Full text
29
Maria, Clément. "Algorithmes et structures de données en topologie algorithmique." Thesis, Nice, 2014. http://www.theses.fr/2014NICE4081/document.
Full textAbstract:
La théorie de l'homologie généralise en dimensions supérieures la notion de connectivité dans les graphes. Étant donné un domaine, décrit par un complexe simplicial, elle définit une famille de groupes qui capturent le nombre de composantes connexes, le nombre de trous, le nombre de cavités et le nombre de motifs équivalents en dimensions supérieures. En pratique, l'homologie permet d'analyser des systèmes de données complexes, interprétés comme des nuages de points dans des espaces métriques. La théorie de l'homologie persistante introduit une notion robuste d'homologie pour l'inférence topologique. Son champ d'application est vaste, et comprend notamment la description d'espaces des configurations de systèmes dynamiques complexes, la classification de formes soumises à des déformations et l'apprentissage en imagerie médicale. Dans cette thèse, nous étudions les ramifications algorithmiques de l'homologie persistante. En premier lieu, nous introduisons l'arbre des simplexes, une structure de données efficace pour construire et manipuler des complexes simpliciaux de grandes dimensions. Nous présentons ensuite une implémentation rapide de l'algorithme de cohomologie persistante à l'aide d'une matrice d'annotations compressée. Nous raffinons également l'inférence de topologie en décrivant une notion de torsion en homologie persistante, et nous introduisons la méthode de reconstruction modulaire pour son calcul. Enfin, nous présentons un algorithme de calcul de l'homologie persistante zigzag, qui est une généralisation algébrique de la persistance. Pour cet algorithme, nous introduisons de nouveaux théorèmes de transformations locales en théorie des représentations de carquois, appelés principes du diamant. Ces algorithmes sont tous implémentés dans la librairie de calcul GudhiThe theory of homology generalizes the notion of connectivity in graphs to higher dimensions. It defines a family of groups on a domain, described discretely by a simplicial complex that captures the connected components, the holes, the cavities and higher-dimensional equivalents. In practice, the generality and flexibility of homology allows the analysis of complex data, interpreted as point clouds in metric spaces. The theory of persistent homology introduces a robust notion of homology for topology inference. Its applications are various and range from the description of high dimensional configuration spaces of complex dynamical systems, classification of shapes under deformations and learning in medical imaging. In this thesis, we explore the algorithmic ramifications of persistent homology. We first introduce the simplex tree, an efficient data structure to construct and maintain high dimensional simplicial complexes. We then present a fast implementation of persistent cohomology via the compressed annotation matrix data structure. We also refine the computation of persistence by describing ideas of homological torsion in this framework, and introduce the modular reconstruction method for computation. Finally, we present an algorithm to compute zigzag persistent homology, an algebraic generalization of persistence. To do so, we introduce new local transformation theorems in quiver representation theory, called diamond principles. All algorithms are implemented in the computational library Gudhi
30
McDonald, Terry Lynn. "Piecewise polynomial functions on a planar region: boundary constraints and polyhedral subdivisions." Texas A&M University, 2003. http://hdl.handle.net/1969.1/3915.
Full textAbstract:
Splines are piecewise polynomial functions of a given order of smoothness r on a triangulated region (or polyhedrally subdivided region) of Rd. The set of splines
of degree at most k forms a vector space Crk() Moreover, a nice way to study
Cr
k()is to embed n Rd+1, and form the cone b of with the origin. It turns
out that the set of splines on b is a graded module Cr b() over the polynomial ring
R[x1; : : : ; xd+1], and the dimension of Cr
k() is the dimension o
This dissertation follows the works of Billera and Rose, as well as Schenck and
Stillman, who each approached the study of splines from the viewpoint of homological
and commutative algebra. They both defined chain complexes of modules such that
Cr(b) appeared as the top homology module.
First, we analyze the effects of gluing planar simplicial complexes. Suppose
1, 2, and = 1 [ 2 are all planar simplicial complexes which triangulate
pseudomanifolds. When 1 \ 2 is also a planar simplicial complex, we use the
Mayer-Vietoris sequence to obtain a natural relationship between the spline modules
Cr(b), Cr (c1), Cr(c2), and Cr( \ 1 \ 2).
Next, given a simplicial complex , we study splines which also vanish on the
boundary of. The set of all such splines is denoted by Cr(b). In this case, we will
discover a formula relating the Hilbert polynomials of Cr(cb) and Cr (b).
Finally, we consider splines which are defined on a polygonally subdivided region
of the plane. By adding only edges to to form a simplicial subdivision , we will
be able to find bounds for the dimensions of the vector spaces Cr
k() for k 0. In
particular, these bounds will be given in terms of the dimensions of the vector spaces
Cr
k() and geometrical data of both and .
This dissertation concludes with some thoughts on future research questions and
an appendix describing the Macaulay2 package SplineCode, which allows the study
of the Hilbert polynomials of the spline modules.
31
Criado, Gallart Francisco [Verfasser], Michael [Akademischer Betreuer] Joswig, Leal Francisco [Akademischer Betreuer] Santos, Michael [Gutachter] Joswig, Günter [Gutachter] Rote, and Leal Francisco [Gutachter] Santos. "Tropical bisectors and diameters of simplicial complexes / Francisco Criado Gallart ; Gutachter: Michael Joswig, Günter Rote, Francisco Santos Leal ; Michael Joswig, Francisco Santos Leal." Berlin : Technische Universität Berlin, 2021. http://d-nb.info/1232319600/34.
Full text
32
Ault, Shaun V. "On the Symmetric Homology of Algebras." The Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1218237992.
Full text
33
Guinard, Stéphane. "Reconstruction et généralisation de complexes simpliciaux à partir de scans lidar de scènes urbaines." Thesis, Paris Est, 2020. http://www.theses.fr/2020PESC2012.
Full textAbstract:
Grâce à leur résolution et à leur accessibilité toujours meilleures, les capteurs LiDAR sont de plus en plus utilisés pour cartographier les villes. En effet, ces capteurs sont capables de réaliser efficacement des acquisitions à haut résolution, qui peuvent ensuite être utilisées pour produire des reconstructions géométriquement détaillées de scènes complexes. Cependant, une telle reconstruction nécessite d’organiser les données avec une structure de données adaptée, comme des nuages de points ou des maillages. Les nuages de points fournissent une représentation compacte des données, mais leur nature discrète empêche certaines applications telles que la visualisation ou la simulation. Les maillages permettent une représentation continue des surfaces, mais ne sont pas bien adaptés à la représentation d’objets complexes, dont le niveau de détail peut dépasser la résolution de l’acquisition. Pour remédier à ces limitations, nous proposons de reconstruire une géométrie continue uniquement lorsque suffisamment d’informations géométriques sont disponibles. Cela nous amène à créer une reconstruction mêlant triangles, arêtes et points. Nous appelons une telle collection d’objets un complexe simplicial. Dans cette thèse, nous étudions la création de modèles 3D de scènes urbaines géométriquement détaillés, basés sur des complexes simpliciaux. Nous montrons que les complexes simpliciaux sont une alternative appropriée aux maillages. En effet, ils sont rapides à calculer et peuvent être simplifiés tout en conservant une grande fidélité géométrique par rapport aux données d’entrée. Nous soutenons que les complexes simples transmettent de précieuses informations géométriques qui peuvent à leur tour être utilisées pour la sémantisation des nuages de points 3D. Nous pensons également qu’ils peuvent servir de base pour des reconstructions multi-échelles de scènes urbaines. Nous présentons d’abord un algorithme efficace pour le calcul de complexes simpliciaux à partir d’acquisitions LiDAR de scènes urbaines. Comme les complexes simpliciaux reconstruits peuvent être très lourds, ils peuvent être difficiles à traiter sur un ordinateur standard. Pour relever ce défi, nous étudions différentes approches pour les généraliser spatialement, en approximant de grandes zones géométriquement simples par des primitives simples. À cette fin, nous proposons un nouvel algorithme pour calculer des approximations planaires par morceaux de nuages de points 3D, basé sur une approche d’optimisation globale. Ensuite, nous proposons deux applications différentes des complexes simpliciaux. La première est une méthode de polygonalisation améliorant la création de modèles 3D légers mais géométriquement précis. La seconde est une méthode de classification faiblement supervisée utilisant des descripteurs 3D locaux et globauxThanks to their ever improving resolution and accessibility, Light Detection And Ranging (LiDAR) sensors are increasingly used for mapping cities. Indeed, these sensors are able to efficiently capture high-density scans, which can then be used to produce geometrically detailed reconstructions of complex scenes. However, such reconstruction requires organizing the scan with a fitting data structure, such as point clouds or meshes. Point clouds provide such a representation in a compact way, but their discrete nature prevents some applications such as visualization or simulation. Meshes allow for a continuous representation of surfaces, but are not well suited for representing complex objects, whose level of detail can exceed the resolution. To address these limitations, we propose to reconstruct a continuous geometry only where sufficient geometric information is available. This leads us to create a reconstruction mixing triangles, edges and points. We call such collection of objects a simplicial complex. In this thesis, we study the creation of geometrically detailed 3-dimensional (3D) models of urban scenes, based on simplicial complexes. We show that simplicial complexes are a suitable alternative to meshes. Indeed, they are fast to compute, and can be simplified while maintaining high geometric geometric fidelity with respect to the input scan. We argue that simplicial complexes convey valuable geometric information which can in turn be used for the semantization of 3D point clouds. We also think that they can serve as input for multi-scale reconstructions of urban scenes. We first present an efficient algorithm for computing simplicial complexes from LiDAR scans of urban scenes. Since the reconstructed simplicial complexes can be very large, they can be difficult to process on a standard computer. To handle this challenge, we investigate different approaches for their spatial generalization by approximating large and geometrically simple areas with simple primitives. To this end, we propose a new algorithm to compute piecewise-planar approximations of 3D point clouds, based on a global optimization approach. Next, we propose two different applications of simplicial complexes. The first one is a polygonalization method improving the creation of light yet geometrically accurate 3D models. The second one is a weakly-supervisedclassification method using 3D local and global descriptors
34
Bigo, Louis. "Représentations symboliques musicales et calcul spatial." Thesis, Paris Est, 2013. http://www.theses.fr/2013PEST1074/document.
Full textAbstract:
Représentations symboliques musicales et calcul spatial. La notion d'espace symbolique est fréquemment utilisée en théorie, analyse et composition musicale. La représentation de séquences dans des espaces de hauteurs, comme le Tonnetz, permet de capturer des propriétés mélodiques et harmoniques qui échappent aux systèmes de représentation traditionnels. Nous généralisons cette approche en reformulant d'un point de vue spatial différents problèmes musicaux (reconnaissance de style, transformations mélodiques et harmoniques, classification des séries tous-intervalles, etc.). Les espaces sont formalisés à l'aide de collections topologiques, une notion correspondant à la décoration d'un complexe cellulaire en topologie algébrique. Un complexe cellulaire per- met la représentation discrète d'un espace à travers un ensemble de cellules topologiques liées les unes aux autres par des relations de voisinage spécifiques. Nous représentons des objets musicaux élémentaires (par exemple des hauteurs ou des accords) par des cellules et construisons un complexe en les organisant suivant une relation de voisinage définie par une propriété musicale. Une séquence musicale est représentée dans un complexe par une trajectoire. L'aspect de la trajectoire révèle des informations sur le style de la pièce et les stratégies de composition employées. L'application d'opérations géométriques sur les trajectoires entraîne des transformations sur la pièce musicale initiale. Les espaces et les trajectoires sont construits à l'aide du langage MGS, un langage de programmation expérimental dédié au calcul spatial, qui vise à introduire la notion d'espace dans le calcul. Un outil, HexaChord, a été développé afin de faciliter l'utilisation de ces notions pour un ensemble prédéfinis d'espaces musicauxMusical symbolic representations and spatial computing. The notion of symbolic space is frequently used in music theory, analysis and composition. Representing sequences in pitch (or chord) spaces, like the Tonnetz, enables to catch some harmonic and melodic properties that elude traditional representation systems. We generalize this approach by rephrasing in spatial terms different musical purposes (style recognition, melodic and harmonic transformations, all-interval series classification, etc.). Spaces are formalized as topological collections, a notion corresponding with the label- ling of a cellular complex in algebraic topology. A cellular complex enables the discrete representation of a space through a set of topological cells linked by specific neighborhood relationships. We represent simple musical objects (for example pitches or chords) by cells and build a complex by organizing them following a particular neighborhood relationship defined by a musical property. A musical sequence is represented in a complex by a trajectory. The look of the trajectory reveals some informations concerning the style of the piece, and musical strategies used by the composer. Spaces and trajectories are computed with MGS, an experimental programming language dedicated to spatial computing, that aims at introducing the notion of space in computation. A tool, HexaChord, has been developped in order to facilitate the use of these notions for a predefined set of musical spaces
35
Bettiol, Enrico. "Column generation methods for quadratic mixed binary programming." Thesis, Paris 13, 2019. http://www.theses.fr/2019PA131073.
Full textAbstract:
La programmation non linéaire mixte peut modéliser un grand nombre de problèmes réels. Cependant, ces problèmes peuvent contenir de nombreuses variables ou contraintes, il convient donc de proposer des méthodes de décomposition afin de les résoudre efficacement. Parmi ces techniques on peut citer la génération de colonnes et notamment la décomposition de Dantzig-Wolfe. Il s’agit d’une reformulation du problème original, qui permet de générer une séquence de sous-problèmes plus simples, appelés maître etpricing, pour obtenir la valeur optimale. Développée d’abord pour les problèmes linéaires, la décomposition de Dantzig-Wolfe peut être généralisée à des problèmes convexes: dans ce contexte, elle est notamment connue sous le nom de décomposition simpliciale. Cette thèse présente des algorithmes de décomposition pour des problèmes quadratiques. La première partie de ce manuscrit est dédiée aux problèmes quadratiques convexes, continus et mixtes binaires. Dans la deuxième partie, des algorithmes pour résoudre des problèmes binaires avec contraintes quadratiques sont présentés. La première partie est consacrée à la résolution de problèmes convexes, quadratiques et continus. Un algorithme basé sur la décomposition simpliciale est proposé: des nouveaux éléments sont ajoutés à la fois au problème maître et au pricing; nous avons testé notre algorithme sur une grande quantité d’instances avec une structure déterminée, et nos résultats montrent que l’algorithme que nous proposons est très efficace par rapport à Cplex, un solveur générique pour ces problèmes. Ce premier travail a été soumis à un journal pour publication. Ensuite, nous étendons cet algorithme aux problèmes convexes mixtes binaires. Nous incorporons la méthode pour le cas continu dans un algorithme de branch and bound qui nous permet d’exploiter des propriétés de notre formulation. Dans ce contexte aussi, des résultats numériques sont fournis: ils montrent que, dans certains cas, les performances de notre algorithme sont efficaces par rapport à Cplex. Ce travail est en préparation pour soumission à un journal. La deuxième partie de cette thèse est dédiée à l’étude d’algorithmes pour des problèmes quadratiques avec contraintes quadratiques. On se concentre sur les problèmes binaires, dont la relaxation continue peut être non convexe. Nous considérons en premier lieu la formulation étendue avec une matrice qui représente les produits des variables. Nous proposons ensuite un algorithme basé sur la décomposition de Dantzig-Wolfe pour obtenir une relaxation dans le Boolean Quadric Polytope (BQP). Ce polytope est connu aussi comme Correlation polytope et il est strictement contenu dans le cône des matrices complètement positives et des matrices semi définies positives. Notre algorithme permet de résoudre cette relaxation, les bornes obtenues sont plus fortes que les bornes SDP et, dans certains cas, les temps de calcul sont comparables ou meilleurs que ceux de BiqCrunch, unsolveur ad-hoc. On montre aussi que la relaxation BQP est une reformulation du problème binaire original, en exploitant un résultat sur les matrices complètement positives, pour les problèmes à contraintes linéaires en égalité. Ensuite, nous considérons des problèmes où les matrices sont décomposables par blocs. On montre aussi que la relaxation BQP est une reformulation du problème binaire original, en exploitant un résultat sur les matrices complètement positives, pour les problèmes à contraintes linéaires en égalité. Ensuite, nous considérons des problèmes où les matrices sont décomposables par blocs. Une relaxation basée sur les blocs est proposée et nous prouvons que cette relaxation est valide pour la relaxation BQP. De plus, prouver l’équivalence entre les deux relaxations est un problème de complétion BQP. La relaxation décomposée par blocs est BQP complétable dans certains cas, mais n’est pas possible dans d’autres cas [....]Non linear programming problems. There are several solution methods in literature for these problems, which are, however, not always efficient in general, in particular for large scale problems. Decomposition strategies such as Column Generation have been developed in order to substitute the original problem with a sequence of more tractable ones. One of the most known of these techniques is Dantzig-Wolfe Decomposition: it has been developed for linear problems and it consists in solving a sequence of subproblems, called respectively master and pricing programs, which leads to the optimum. This method can be extended to convex non linear problems and a classic example of this, which can be seen also as a generalization of the Frank-Wolfe algorithm, is Simplicial Decomposition(SD).In this thesis we discuss decomposition algorithms for solving quadratic optimization problems. In particular, we start with quadratic convex problems, both continuous and mixed binary. Then we tackle the more general class of binary quadratically constrained, quadratic problems. In the first part, we concentrate on SD based-methods for continuous, convex quadratic programming. We introduce new features in the algorithms, for both the master and the pricing problems of the decomposition, and provide results for a wide set of instances, showing that our algorithm is really efficient if compared to the state-of-the-art solver Cplex. This first work is accepted for publication in the journal Computational Optimization and Applications.We then extend the SD-based algorithm to mixed binary convex quadratic problems;we embed the continuous algorithm in a branch and bound scheme that makes us able to exploit some properties of our framework. In this context again we obtain results which show that in some sets of instances this algorithm is still more efficient than Cplex,even with a very simple branch and bound algorithm. This work is in preparation for submission to a journal. In the second part of the thesis, we deal with a more general class of problems, that is quadratically constrained, quadratic problems, where the constraints can be quadratic and both the objective function and the constraints can be non convex. For this class of problems we extend the formulation to the matrix space of the products of variables; we study an algorithm based on Dantzig-Wolfe Decomposition that exploits a relaxation on the Boolean Quadric Polytope (BQP), which is strictly contained in the Completely Positive cone and hence in the cone of positive semi definite (PSD) matrices. This is a constructive algorithm to solve the BQP relaxation of a binary problem an dwe obtain promising results for the root node bound for some quadratic problems. We compare our results with those obtained by the Semi definite relaxation of the ad-hocsolver BiqCrunch. We also show that, for linearly constrained quadratic problems, our relaxation can provide the integer optimum, under certain assumptions. We further study block decomposed matrices and provide results on the so-called BQP-completion problem ; these results are connected to those of PSD and CPP matrices. We show that, given a BQP matrix with some unspecified elements, it can be completed to a full BQP matrix under some assumptions on the positions of the specified elements. This result is related to optimization problems. We propose a BQP-relaxation based on the block structure of the problem. We prove that it provides a lower bound for the previously introduced relaxation, and that in some cases the two formulations are equivalent. We also conjecture that the equivalence result holds if and only if its so-called specification graph is chordal. We provide computational results which show the improvement in the performance of the block-based relaxation, with respect to the unstructured relaxation, and which support our conjecture. This work is in preparation for submission to a journal
36
Adimoolam, Santosh Arvind. "A Calculus of Complex Zonotopes for Invariance and Stability Verification of Hybrid Systems." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM027/document.
Full textAbstract:
Le calcul des ensembles atteignables est une approche de facto utilisée dans de nombreuses méthodes de vérification formelles pour les systèmes hybrides. Mais le calcul exact de l'ensemble atteignable est un problème insurmontable pour de nombreux types de systèmes hybrides, soit en raison de l'indécidabilité ou de la complexité de calcul élevée. Alternativement, beaucoup de recherches ont été axées sur l'utilisation de représentations d'ensembles qui peuvent être manipulées efficacement pour calculer une surestimation suffisamment précise de l'ensemble atteignable. Les zonotopes sont une représentation utile de l'ensemble dans l'analyse de l'accessibilité en raison de leur fermeture et de leur faible complexité pour le calcul de la transformation linéaire et des opérations sommaires de Minkowski. Mais pour approximer les ensembles de temps non bornés atteignables par des invariants positifs, les zonotopes ont l'inconvénient suivant. L'efficacité d'une représentation d'ensemble pour calculer un invariant positif dépend de l'encodage efficace des directions de convergence des états vers un équilibre. Dans un système hybride affine, certaines des directions de convergence peuvent être codées par les vecteurs propres à valeur complexe des matrices de transformation. Mais la représentation zonotopique ne peut pas exploiter la structure propre complexe des matrices de transformation car elle n'a que des générateurs à valeur réelle.Par conséquent, nous étendons les zonotopes réels au domaine de valeur complexe d'une manière qui peut capturer la contraction le long de vecteurs évalués complexes. Cela donne une nouvelle représentation d'ensemble appelée zonotope complexe. Géométriquement, les zonotopes complexes représentent une classe plus large d'ensembles qui comprennent des ensembles non polytopiques ainsi que des zonotopes polytopiques. Ils conservent le mérite des zonotopes réels que nous pouvons effectuer efficacement la transformation linéaire et les opérations sommaires de Minkowski et calculer la fonction de support. De plus, nous montrons qu'ils peuvent capturer la contraction le long de vecteurs propres complexes. De plus, nous développons des approximations traitables par calcul pour la vérification d'inclusion et l'intersection avec des demi-espaces. En utilisant ces opérations sur des zonotopes complexes, nous développons des programmes convexes pour vérifier les propriétés d'invariance linéaire des systèmes hybrides affines à temps discret et la stabilité exponentielle des systèmes impulsifs linéaires. Nos expériences sur certains exemples de benchmarks démontrent l'efficacité des techniques de vérification basées sur des zonotopes complexesComputing reachable sets is a de facto approach used in many formal verification methods for hybrid systems. But exact computation of the reachable set is an in- tractable problem for many kinds of hybrid systems, either due to undecidability or high computational complexity. Alternatively, quite a lot of research has been focused on using set representations that can be efficiently manipulated to com- pute sufficiently accurate over-approximation of the reachable set. Zonotopes are a useful set representation in reachability analysis because of their closure and low complexity for computing linear transformation and Minkowski sum operations. But for approximating the unbounded time reachable sets by positive invariants, zonotopes have the following drawback. The effectiveness of a set representation for computing a positive invariant depends on efficiently encoding the directions for convergence of the states to an equilibrium. In an affine hybrid system, some of the directions for convergence can be encoded by the complex valued eigen- vectors of the transformation matrices. But the zonotope representation can not exploit the complex eigenstructure of the transformation matrices because it only has real valued generators.Therefore, we extend real zonotopes to the complex valued domain in a way that can capture contraction along complex valued vectors. This yields a new set representation called complex zonotope. Geometrically, complex zonotopes repre- sent a wider class of sets that include some non-polytopic sets as well as polytopic zonotopes. They retain the merit of real zonotopes that we can efficiently perform linear transformation and Minkowski sum operations and compute the support function. Additionally, we show that they can capture contraction along complex valued eigenvectors. Furthermore, we develop computationally tractable approx- imations for inclusion-checking and intersection with half-spaces. Using these set operations on complex zonotopes, we develop convex programs to verify lin- ear invariance properties of discrete time affine hybrid systems and exponential stability of linear impulsive systems. Our experiments on some benchmark exam- ples demonstrate the efficiency of the verification techniques based on complex zonotopes
37
Calvez, Philippe. "Modélisation d'agencements énergétiques durables dans les zones urbaines intelligentes : une approche pour la réduction de l’emprise énergétique par les pratiques soutenables." Thesis, Paris 1, 2015. http://www.theses.fr/2015PA010056.
Full textAbstract:
D’un côté, la transition écologique et les enjeux de développement durable sont de nos jours une réalité que l’on ne peut ignorer compte tenu des impacts négatifs des activités humaines sur leurs environnements. De l’autre côté, une numérisation toujours plus importante de ces environnements entraîne la génération de volumes massifs de traces numériques, qui sont autant d’indices sur le monde dans lequel vivent les acteurs de ces activités. Une difficulté non négligeable existe pour comprendre les tenants et aboutissants faisant que d’une activité à une autre, l’impact sur l’environnement mesuré dans ces travaux de recherche à travers le concept d’Emprise Énergétique (EmE) n’est pas le même. Notre approche considère l’identification sur la base de ces traces numériques, d’activité d’entités humaines et non humaines. L’instanciation de ces dernières au sein de pratiques mobilise des ressources (physiques et virtuelles) en plus ou moins grand nombre. Leurs modélisations permettraient de mieux appréhender les enjeux liés à la transition écologique. Identifier sur la base d’indicateurs quantifiables les pratiques ayant un impact réduit sur l’environnement serait une piste permettant de contribuer à cette transition. Ces pratiques, au sens de coordination de multiples entités hétérogènes dans le temps et l’espace, peuvent être formalisées sous forme de structures d’activités multidimensionnelles à l’aide de la théorie de l’Agencement et d’un ensemble d’outils mathématiques (Complexes Simpliciaux, Hypernetworks). Ces travaux de recherche tentent de modéliser le phénomène d’activité humaine et non humaine en s’appuyant sur la caractérisation du contexte de celles-ci à partir de données massives. Ces agencements sont calculés et représentés dans une application (IMhoTEP) ayant pour but de construire ces structures complexes non pas sur des catégorisations faites a priori des entités, mais en se focalisant sur les relations que celles-ci entretiennent dans plusieurs dimensions. L’objectif final est de proposer un outil d’accompagnement à la transition écologique à destination des acteurs participant à des activités induisant la consommation, voire la production de ressources. Ces travaux de recherche en informatique s’appuient sur la numérisation continue des espaces et particulièrement les espaces urbains (Smart City, Internet of Everything)On one hand, the ecological transition and sustainable development issues are today a reality that cannot be ignored given the negative impacts of human activities on their environments. On the other side, an increasingly important digitization of these environments results in the generation of massive volumes of digital traces, which are all signs of actors’ activities. A significant challenge is to understand the ins and outs of environmental impact due activities and considering Emprise of Energy (EmE) as a key indicator and how this indicator can strongly change from an activity to another. Our approach considers the identification of Practice on the basis of these digital traces generated by human and non-human entities during specific activities. Practice (instantiation of activity) uses more or less resources (physical and virtual) during their existence. Be able to identify which one is more resources dependent would help to better understand how to promote ecological transition. Promoting or at least identifying on the basis of quantifiable indicators (i.e Energy Emprise), practices that have a low impact on the environment, could be an innovative approach. These practices, in the sense of coordination of multiple heterogeneous entities in time and space, can be formalized in the form of multidimensional structures activities - Hypergraph of Activities – using the theory of Assemblage (Agencement in french) and using a set of mathematical tool (Simplicial Complexes, Hypernetworks). This research attempts to model the phenomenon of human and not human activity based on the characterization of the context (massive contextual data). These Assemblages are calculated and represented in an research application (IMhoTEP) which aims to build these complex structures not based on a priori entities’ classification, but by focusing on the relationships that they maintain in several dimensions. The main goal is to offer a decision tool which support actors’ ecological transition by understand activities inducing consumption or production of resources. These academic research in the field of computer science is based continuous digitization of physical and virtual spaces, particularly highly connected urban areas (Smart City, Internet of Everything)
38
Poncio, Carlos Henrique Felicio. "Versões do teorema de Tverberg e aplicações." Universidade Federal de São Carlos, 2016. https://repositorio.ufscar.br/handle/ufscar/8044.
Full textAbstract:
Submitted by Livia Mello (liviacmello@yahoo.com.br) on 2016-10-05T14:40:49Z
No. of bitstreams: 1
DissCHFP.pdf: 1216039 bytes, checksum: e21e062b0283d2bfe6ec436442e824a5 (MD5)Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:23:38Z (GMT) No. of bitstreams: 1 DissCHFP.pdf: 1216039 bytes, checksum: e21e062b0283d2bfe6ec436442e824a5 (MD5)
Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:23:43Z (GMT) No. of bitstreams: 1 DissCHFP.pdf: 1216039 bytes, checksum: e21e062b0283d2bfe6ec436442e824a5 (MD5)
Made available in DSpace on 2016-10-20T19:23:50Z (GMT). No. of bitstreams: 1 DissCHFP.pdf: 1216039 bytes, checksum: e21e062b0283d2bfe6ec436442e824a5 (MD5) Previous issue date: 2016-02-25
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
In this work, we will use topological methods in combinatorics and geometry to present a proof of the topological Tverberg theorem and a result about many Tverberg partitions.
O objetivo principal desta dissertação consiste em desenvolver um estudo detalhado de métodos topológicos em combinatória e geometria visando apresentar uma prova da versão topológica do teorema de Tverberg e de um teorema sobre a quantidade de partições de Tverberg.
FAPESP: 2015/01264-7
39
Buchet, Mickaël. "Topological inference from measures." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112367/document.
Full textAbstract:
La quantité de données disponibles n'a jamais été aussi grande. Se poser les bonnes questions, c'est-à-dire des questions qui soient à la fois pertinentes et dont la réponse est accessible est difficile. L'analyse topologique de données tente de contourner le problème en ne posant pas une question trop précise mais en recherchant une structure sous-jacente aux données. Une telle structure est intéressante en soi mais elle peut également guider le questionnement de l'analyste et le diriger vers des questions pertinentes. Un des outils les plus utilisés dans ce domaine est l'homologie persistante. Analysant les données à toutes les échelles simultanément, la persistance permet d'éviter le choix d'une échelle particulière. De plus, ses propriétés de stabilité fournissent une manière naturelle pour passer de données discrètes à des objets continus. Cependant, l'homologie persistante se heurte à deux obstacles. Sa construction se heurte généralement à une trop large taille des structures de données pour le travail en grandes dimensions et sa robustesse ne s'étend pas au bruit aberrant, c'est-à-dire à la présence de points non corrélés avec la structure sous-jacente.Dans cette thèse, je pars de ces deux constatations et m'applique tout d'abord à rendre le calcul de l'homologie persistante robuste au bruit aberrant par l'utilisation de la distance à la mesure. Utilisant une approximation du calcul de l'homologie persistante pour la distance à la mesure, je fournis un algorithme complet permettant d'utiliser l'homologie persistante pour l'analyse topologique de données de petite dimension intrinsèque mais pouvant être plongées dans des espaces de grande dimension. Précédemment, l'homologie persistante a également été utilisée pour analyser des champs scalaires. Ici encore, le problème du bruit aberrant limitait son utilisation et je propose une méthode dérivée de l'utilisation de la distance à la mesure afin d'obtenir une robustesse au bruit aberrant. Cela passe par l'introduction de nouvelles conditions de bruit et l'utilisation d'un nouvel opérateur de régression. Ces deux objets font l'objet d'une étude spécifique. Le travail réalisé au cours de cette thèse permet maintenant d'utiliser l'homologie persistante dans des cas d'applications réelles en grandes dimensions, que ce soit pour l'inférence topologique ou l'analyse de champs scalairesMassive amounts of data are now available for study. Asking questions that are both relevant and possible to answer is a difficult task. One can look for something different than the answer to a precise question. Topological data analysis looks for structure in point cloud data, which can be informative by itself but can also provide directions for further questioning. A common challenge faced in this area is the choice of the right scale at which to process the data.One widely used tool in this domain is persistent homology. By processing the data at all scales, it does not rely on a particular choice of scale. Moreover, its stability properties provide a natural way to go from discrete data to an underlying continuous structure. Finally, it can be combined with other tools, like the distance to a measure, which allows to handle noise that are unbounded. The main caveat of this approach is its high complexity.In this thesis, we will introduce topological data analysis and persistent homology, then show how to use approximation to reduce the computational complexity. We provide an approximation scheme to the distance to a measure and a sparsifying method of weighted Vietoris-Rips complexes in order to approximate persistence diagrams with practical complexity. We detail the specific properties of these constructions.Persistent homology was previously shown to be of use for scalar field analysis. We provide a way to combine it with the distance to a measure in order to handle a wider class of noise, especially data with unbounded errors. Finally, we discuss interesting opportunities opened by these results to study data where parts are missing or erroneous
40
Benzeghli, Brahim. "Étude explicite de quelques n-champs géométriques." Phd thesis, Université Nice Sophia Antipolis, 2013. http://tel.archives-ouvertes.fr/tel-00868795.
Full textAbstract:
Dans [PRID], Pridham a montré que tout n-champs d'Artin M admet une présentation en tant que schéma simplicial X. → M, telle que le schéma simplicial X satisfait à certaines propriétés notées par G.Pn,k de [GROTH]. Dans la présentation (...→ X2 → X1 → X0 → M), le schéma X1 représente une carte pour X0 x MX0. Donc, la lissité de X0 → M est équivalente à la lissité des deux projections ә0,ә1 : X1 → X0. Ce sont les deux premières parties de la condition de Grothendieck-Pridham, notées G.P1,0 et G.P1,1. Dans [BENZ12] nous avons introduit un n-champ d'Artin M des éléments de Maurer-Cartan d'une dg-catégorie. On a construit une carte, et on a déjà fait la preuve des premières conditions de lissité explicitement. Pour tout n et tout 0 ≤ k ≤ n Pridham considère un schéma noté MatchΛkn(X) avec un morphisme Xn → MatchΛkn(X). On construira explicitement le schéma simplicial de Grothendieck-Pridham X, on montrera la lissité formelle de cette carte précédente, ainsi que M est un n-champ géométrique.
41
Brunink, Jan-Marten. "Subdivisions of simplicial complexes." Doctoral thesis, 2021. https://repositorium.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-202109145342.
Full textAbstract:
The topic of this thesis are subdivisions of simplicial complexes, in particular we focus on the so-called antiprism triangulation. In the first main part, the real-rootedness of the h-polynomial of the antiprism triangulation of the simplex is proven. Furthermore, we study combinatorial interpretations of several invariants as the h- and local h-vector. In the second part, we show the almost strong Lefschetz property of the antiprism triangulation for every shellable simplicial complex.
42
Huntemann, Svenja. "Simplicial Complexes of Placement Games." 2013. http://hdl.handle.net/10222/35472.
Full textAbstract:
Placement games are a subclass of combinatorial games which are played on graphs. In this thesis, we demonstrate that placement games could be considered as games played on simplicial complexes. These complexes are constructed using square-free monomials.
We define new classes of placement games and the notion of Doppelgänger. To aid in exploring the simplicial complex of a game, we introduce the bipartite flip and develop tools to compare known bounds on simplicial complexes (such as the Kruskal-Katona bounds) with bounds on game complexes.
43
Couto, Maria Inês Gomes da Rocha. "Measuring Distances Between Paving Simplicial Complexes." Master's thesis, 2018. https://hdl.handle.net/10216/114586.
Full text
44
Akinwande, Grace Itunuoluwa. "Limit Theorems for Random Simplicial Complexes." Doctoral thesis, 2020. https://repositorium.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-202010223623.
Full textAbstract:
We consider random simplicial complexes constructed on a Poisson point process within a convex set in a Euclidean space, especially the Vietoris-Rips complex and the Cech complex both of whose 1-skeleton is the Gilbert graph. We investigate at first the Vietoris-Rips complex by considering the volume-power functionals defined by summing powers of the volume of all k-dimensional faces in the complex. The asymptotic behaviour of these functionals is investigated as the intensity of the underlying Poisson point process tends to infinity and the distance parameter goes to zero. This behaviour is observed in different regimes. Univariate and multivariate central limit theorems are proven, and analogous results for the Cech complex are then given. Finally we provide a Poisson limit theorem for the components of the f-vector in the sparse regime.
45
Couto, Maria Inês Gomes da Rocha. "Measuring Distances Between Paving Simplicial Complexes." Dissertação, 2018. https://hdl.handle.net/10216/114586.
Full text
46
Steenbergen, John Joseph. "Towards a Spectral Theory for Simplicial Complexes." Diss., 2013. http://hdl.handle.net/10161/8256.
Full textAbstract:
In this dissertation we study combinatorial Hodge Laplacians on simplicial com-
plexes using tools generalized from spectral graph theory. Specifically, we consider
generalizations of graph Cheeger numbers and graph random walks. The results in
this dissertation can be thought of as the beginnings of a new spectral theory for
simplicial complexes and a new theory of high-dimensional expansion.
We first consider new high-dimensional isoperimetric constants. A new Cheeger-
type inequality is proved, under certain conditions, between an isoperimetric constant
and the smallest eigenvalue of the Laplacian in codimension 0. The proof is similar
to the proof of the Cheeger inequality for graphs. Furthermore, a negative result is
proved, using the new Cheeger-type inequality and special examples, showing that
certain Cheeger-type inequalities cannot hold in codimension 1.
Second, we consider new random walks with killing on the set of oriented sim-
plexes of a certain dimension. We show that there is a systematic way of relating
these walks to combinatorial Laplacians such that a certain notion of mixing time
is bounded by a spectral gap and such that distributions that are stationary in a
certain sense relate to the harmonics of the Laplacian. In addition, we consider the
possibility of using these new random walks for semi-supervised learning. An algo-
rithm is devised which generalizes a classic label-propagation algorithm on graphs to
simplicial complexes. This new algorithm applies to a new semi-supervised learning
problem, one in which the underlying structure to be learned is flow-like.
Dissertation
47
Perkins, Simon James. "Field D* Pathfinding in Weighted Simplicial Complexes." Thesis, 2014. http://pubs.cs.uct.ac.za/archive/00000924/.
Full textAbstract:
The development of algorithms to efficiently determine an optimal path through a complex environment is a continuing area of research within Computer Science. When such environments can be represented as a graph, established graph search algorithms, such as Dijkstra’s shortest path and A*, can be used. However, many environments are constructed from a set of regions that do not conform to a discrete graph. The Weighted Region Problem was proposed to address the problem of finding the shortest path through a set of such regions, weighted with values representing the cost of traversing the region.
Robust solutions to this problem are computationally expensive since finding shortest paths across a region requires expensive minimisation. Sampling approaches construct graphs by introducing extra points on region edges and connecting them with edges criss-crossing the region. Dijkstra or A* are then applied to compute shortest paths. The connectivity of these graphs is high and such techniques are thus not particularly well suited to environments where the weights and representation frequently change.
The Field D* algorithm, by contrast, computes the shortest path across a grid of weighted square cells and has replanning capabilites that cater for environmental changes. However, representing an environment as a weighted grid (an image) is not space-efficient since high resolution is required to produce accurate paths through areas containing features sensitive to noise.
In this work, we extend Field D* to weighted simplicial complexes – specifically – triangulations in 2D and tetrahedral meshes in 3D.
Such representations offer benefits in terms of space over a weighted grid, since fewer triangles can represent polygonal objects with greater accuracy than a large number of grid cells. By exploiting these savings, we show that Triangulated Field D* can produce an equivalent path cost to grid-based Multi-resolution Field D*, using up to an order of magnitude fewer triangles over grid cells and visiting an order of magnitude fewer nodes.
Finally, as a practical demonstration of the utility of our formulation, we show how Field D* can be used to approximate a distance field on the nodes of a simplicial complex, and how this distance field can be used to weight the simplicial complex to produce contour-following behaviour by shortest paths computed with Field D*.
48
Venturello, Lorenzo. "Combinatorial and algebraic properties of balanced simplicial complexes." Doctoral thesis, 2019. https://repositorium.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-201911192203.
Full textAbstract:
Simplicial complexes are mathematical objects whose importance stretches from topology to commutative algebra and combinatorics. In this thesis we focus on the family of balanced simplicial complexes. A d-dimensional simplicial complex is balanced if its 1-skeleton can be properly (d+1)-colored, as in the classical graph theoretic sense. Equivalently, a d-dimensional complex is balanced iff it admits a non-degenerate simplicial projection to the d-simplex. We present results on these complexes from a number of different points of view. After two introductory chapters, we exhibit in chapter 3 an infinite family of balanced counterexamples to Stanley's partitionability conjecture. These complexes, which are in addition constructible, answer a question of Duval et al. in the negative. Next we shift to combinatorial topology, and study cross-flips, i.e., local moves on balanced manifolds introduced by Izmestiev, Klee and Novik, which preserve both the coloring and the topological type. In chapter 4 we provide an explicit description and enumeration of an interesting subset of these moves and use it to prove a Pachner-type theorem. Indeed, we show that any two balanced combinatorial manifolds with boundary which are PL-homeomorphic can be transformed one into the other by a sequence of shellings and inverse shellings which preserve both the coloring and the topological type at each step. This solves a problem proposed by Izmestiev, Klee and Novik. Chapter 5 is devoted to the study of certain algebraic invariants of simplicial complexes in the balanced case. Here upper bounds for the graded Betti numbers of the Stanley-Reisner ring of balanced simplicial complexes are investigated in several level of generalities, and we show that they are sharper than in the general case. First, we employ Hochster formula to obtain inequalities for the case of arbitrary balanced complexes. Next, we focus on the balanced Cohen-Macaulay case and we obtain two upper bounds via two different strategies. Using similar ideas we also bound the Betti numbers in the linear strand of balanced normal d-pseudomanifolds, for d>2. Finally, we explicitly compute graded Betti numbers of the class of stacked cross-polytopal spheres, and conjecture that they provide a sharp upper bound for those of all balanced pseudomanifolds with the same dimension and number of vertices. In the last chapter, we implement cross-flips on balanced surfaces and 3-manifolds, and use this computer program to search for balanced manifolds on few vertices, possibly vertex-minimal. Reducing the barycentric subdivision of vertex minimal triangulations, we find a long list of balanced triangulations of interesting spaces on few vertices. Among those stand out a balanced vertex-minimal triangulation of the dunce hat (11-vertices) and of the 2- and 3-dimensional real projective space (9 and 16 vertices respectively). Using obstructions from knot theory and a careful choice of flips we find a balanced non-shellable 3-sphere and a balanced shellable non-vertex-decomposable 3-sphere on 28 and 22 vertices respectively. These are the smallest instances known in the literature.
49
Shih, Jen-Chieh, and 施仁傑. "The simplicial complexes and the multiplicity of determinantal rings." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/58212839789821132963.
Full textAbstract:
碩士國立中正大學
數學研究所
89
Let K be a field and X be a generic m ×n matrix over K. Let R=K[X] and I be the ideal generated by the (r+1) ×(r+1) minors of X. There are several ways to prove the above formula since 1950, however, they are not easy to understand. In this paper, we use the simplicial complexes to simplify our difficulty. We are able to quickly calculate the multiplicity of R.
50
Crowley, Katherine Dutton. "Discrete Morse theory and the geometry of nonpositively curved simplicial complexes." Thesis, 2001. http://hdl.handle.net/1911/17951.
Full textAbstract:
Understanding the conditions under which a simplicial complex collapses is a central issue in many problems in topology and combinatorics. Let K be a simplicial complex endowed with the piecewise Euclidean geometry given by declaring edges to have unit length, and satisfying the property that every 2-simplex is a face of at most two 3-simplices in K. Our main theorem is that if |K| is nonpositively curved (in the sense of CAT(0)) then K simplicially collapses to a point. The main tool used in the proof is Forman's discrete Morse theory (see section 2.2), a combinatorial version of the classical smooth theory. A key ingredient in our proof is a combinatorial analog of the fact that a minimal surface in R3 has nonpositive Gauss curvature (see theorem 28). We also investigate another combinatorial question related to curvature. We prove a combinatorial isoperimetric inequality by finding an exact answer for the largest possible number of interior vertices in a triangulated n-gon satisfying the property that every interior vertex has degree at least six.