Dans ce travail, nous étudions le cadre de la morphologie mathématique sur les complexes simpliciaux. Complexes simpliciaux sont une structure versatile et largement utilisée pour représenter des données multidimensionnelles, telles que des maillages, qui sont des complexes tridimensionnels, ou des graphes, qui peuvent être interprétées comme des complexes bidimensionnels. La morphologie mathématique est l'un des cadres les plus puissants pour le traitement de l'image, y compris le traitement des structures numériques, et est largement utilisé pour de nombreuses applications. Toutefois, les opérateurs de morphologie mathématique sur des espaces complexes simpliciaux n'est pas un concept entièrement développé dans la littérature. Dans ce travail, nous passons en revue certains opérateurs classiques des complexes simpliciaux sous la lumière de la morphologie mathématique, de montrer qu'ils sont des opérateurs de morphologie. Nous définissons certains treillis de base et les opérateurs agissant sur ces treillis: dilatations, érosions, ouvertures, fermetures et filtres alternés séquentiels, et aussi leur extension à simplexes pondérés. Cependant, les principales contributions de ce travail sont ce que nous appelions les opérateurs dimensionnels, petites et polyvalents opérateurs qui peuvent être utilisés pour définir de nouveaux opérateurs sur les complexes simpliciaux, qui garde les propriétés de la morphologie mathématique. Ces opérateurs peuvent également être utilisés pour exprimer pratiquement n'importe quel opérateur dans la littérature. Nous illustrons les opérateurs définis et nous comparons les filtres alternés séquentiels contre filtres définis dans la littérature, où nos filtres présentent de meilleurs résultats pour l'enlèvement du petit, intense bruit des images binaires / 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

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 musicaux / Musical 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

Cette thèse traite du problème de séparation aveugle de sources non-négatives (c'est à dire des grandeurs positives ou nulles). La situation de séparation de mélanges linéaires instantanés de sources non-négatives se rencontre dans de nombreux problèmes de traitement de signal et d'images, comme la décomposition de signaux mesurés par un spectromètre (spectres de masse, spectres Raman, spectres infrarouges), la décomposition d'images (médicales, multi-spectrale ou hyperspectrales) ou encore l'estimation de l'activité d'un radionucléide. Dans ces problèmes, les grandeurs sont intrinsèquement non-négatives et cette propriété doit être préservée lors de leur estimation, car c'est elle qui donne un sens physique aux composantes estimées. La plupart des méthodes existantes de séparation de sources non-négatives requièrent de ''fortes" hypothèses sur les sources (comme l'indépendance mutuelle, la dominance locale ou encore l'additivité totale des sources), qui ne sont pas toujours vérifiées en pratique. Dans ce travail, nous proposons une nouvelle méthode de séparation de sources non-négatives fondée sur la répartition géométrique du nuage des observations. Les coefficients de mélange et les sources sont estimées en cherchant le cône simplicial d'ouverture minimale contenant le nuage des observations. Cette méthode ne nécessite pas l'indépendance mutuelle des sources, ni même leur décorrélation; elle ne requiert pas non plus la dominance locale des sources, ni leur additivité totale. Une seule condition est nécessaire et suffisante: l'orthant positif doit être l'unique cône simplicial d'ouverture minimale contenant le nuage de points des signaux sources. L'algorithme proposé est évalué avec succès dans deux situations de séparation de sources non-négatives de nature très différentes. Dans la première situation, nous effectuons la séparation de spectres de masse mesurés à la sortie d'un chromatographe liquide haute précision, afin d'identifier et quantifier les différents métabolites (petites molécules) présents dans l'urine d'un rat traité au phénobarbital. Dans la deuxième situation, nous estimons les différents compartiments pharmacocinétiques du radio-traceur FluoroDeoxyGlucose marqué au fluor 18 ([18F]-FDG) dans le cerveau d'un patient humain, à partir d'une série d'images 3D TEP de cet organe. Parmi ces pharmacocinétiques, la fonction d'entrée artérielle présente un grand intérêt pour l'évaluation de l'efficacité d'un traitement anti-cancéreux en oncologie.

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.

This thesis examines graph polynomials and particularly their complexity. We give short proofs of two results from Gessel and Sagan (1996) which present new evaluations of the Tutte polynomial concerning orientations. A theorem of Massey et al (1997) gives an expression concerning the average size of a forest in a graph. We generalise this result to any simplicial complex. We answer a question posed by Kleinschmidt and Onn (1995) by showing that the language of partitionable simplicial complexes is in NP. We prove the following result concerning the complexity of the Tutte polynomial: Theorem 1. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers x and y, and evaluate the Tutte polynomial, T(G;x,y). The rank generating function S of a graphic 2-polymatroid was introduced by Oxley and Whittle (1993). It has many similarities to the Tutte polynomial and we prove the following results. Theorem 2. Evaluating S at a fixed point (u,v) is #P-hard unless uv=1 when there is a polynomial time algorithm. Theorem 3. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers u and v, and evaluate S(G;u,v). We consider a class of graphs $S$, which are those graphs which are obtainable from a graph with no edges using the unsigned version of Reidemeister moves. We examine the relationship between this class and other similarly defined classes such as the delta-wye graphs. There remain many open questions such as whether S contains every graph. However we have an invariant of the moves, based on the Tutte polynomial, which allows us to determine from which graph with no edges, if any, a particular graph can be obtained. Finally we consider a new polynomial on weighted graphs which is motivated by the study of weight systems on chord diagrams. We give three states model and a recipe theorem. An unweighted version of this polynomial is shown to contain as specialisations, a wide range of graph invariants, such as the Tutte polynomial, the polymatroid polynomial of Oxley and Whittle (1993) and the symmetric function generalisation of the chromatic polynomial introduced by Stanley (1995). We close with a discussion of complexity issues proving hardness results for very restricted classes of graphs.

Η παρούσα διατριβή αφορά στη μελέτη του συνόρου υπερβολικών δισδιάστατων πολυέδρων. Οι χώροι οι οποίοι μελετώνται κατασκευάζονται κολλώντας υπερβολικά τρίγωνα τα οποία έχουν 2 τουλάχιστον κορυφές στο άπειρο. Οι συγκολλήσεις γίνονται με ισομετρίες κατά μήκος των πλευρών των τριγώνων και οι χώροι οι οποίοι προκύπτουν εφοδιάζονται φυσιολογικά με μία γεωμετρία η οποία έχει ομοιότητες με την γεωμετρία των υπερβολικών πολλαπλοτήτων. Αρχικά μελετάμε τις βασικές ιδιότητες των δισδιάστατων ιδεωδών πολυέδρων και αποδεικνύουμε ότι: «Για κάθε δύο σημεία του συνόρου του καθολικού καλύμματος του χώρου που κατασκευάζουμε, υπάρχει άπειρο πλήθος υποχώρων του συνόρου ομοιομορφικών με το οι οποίοι περιέχουν τα σημεία αυτά». Στη συνέχεια, για μια ειδική κλάση πολυέδρων που κατασκευάζουμε κολλώντας με ισομετρίες κατά μήκος των πλευρών τους πεπερασμένα υπερβολικά τρίγωνα τα οποία έχουν δύο κορυφές στο άπειρο, αποδεικνύουμε επιπλέον ότι: «το σύνορο του καθολικού καλύμματος του χώρου που κατασκευάζουμε είναι τοπικά συνεκτικό κατά τόξα». Τέλος, στην τρίτη ενότητα δίδουμε μια τοπολογική περιγραφή του συνόρου των ιδεωδών πολυέδρων διάστασης 2. / The present work is related to the study of the visual boundary of hyperbolic two dimensional simplicial complexes. We construct (and study) spaces by gluing hyperbolic triangles with at least two vertices at infinity. We glue the triangles by isometries along their sides and we study the derived spaces. In the first chapter it is proved that for every two points in the visual boundary of the universal covering of a two dimensional ideal polyhedron, there is an infinity of paths joining them. In the second chapter, a class of hyperbolic two dimensional complexes X is defined. Is is shown that the limit set of the action of π1(X) on the universal covering of X, is equal to the visual boundary and also that the visual boundary is path connected and locally path connected. Finally, in the third chapter a kind of Sierpinski set is described which is homeomorphic to the visual boundary of certain ideal polyhedra.

1 Topological and Geometrical Combinatorics Martin Tancer Abstract The task of the thesis is to present several new results on topological methods in combinatorics. The results can be split into two main streams. The first stream regards intersection patterns of convex sets. It is shown in the thesis that finite projective planes cannot be intersection patterns of convex sets of fixed dimension which answers a question of Alon, Kalai, Matoušek and Meshulam. Another result shows that d-collapsibility (a necessary condition on properties of in- tersection patterns of convex sets in dimension d) is NP-complete for recognition if d ≥ 4. In addition it is shown that d-collapsibility is not a necessary condition on properties of intersection patterns of good covers, which disproves a conjecture of G. Wegner from 1975. The second stream considers algorithmic hardness of recognition of simplicial com- plexes embeddable into Rd . The following results are proved: It is algorithmically un- decidable whether a k-dimensional simplicial complex piecewise-linearly embeds into Rd for d ≥ 5 and k ∈ {d−1, d}; and this problem is NP-hard if d ≥ 4 and d ≥ k ≥ 2d−2 3 .

<p>U ovoj tezi razvijen je formalni sistem za dokazivanje teorema<br />incidencije u projektivnoj geometiji. Osnova sistema je Čeva/Menelaj<br />metod za dokazivanje teorema incidencije. Formalizacija o kojoj je<br />ovdje riječ izvedena je korišćenjem &Delta;-kompleksa, pa su tako u<br />disertaciji spojene oblasti logike, geometrije i algebarske<br />topologije. Aksiomatski sekventi proizilaze iz 2-ciklova &Delta;-kompleksa.<br />Definisana je Euklidska i projektivna interpretacija sekvenata i<br />dokazana je saglasnost i odlučivost sistema. Dati su primjeri<br />iščitavanja teorema incidencije iz dokazivih sekvenata sistema. U<br />tezi je data i procedura za provjeru da li je skup od n šestorki tačaka<br />aksiomatski sekvent.</p> / <p>In this thesis, a formal sequent system for proving incidence theorems in<br />projective geometry is introduced. This system is based on the<br />Ceva/Menelaus method for proving theorems. This formalization is performed<br />using &Delta;-complexes, so the areas of logic, geometry and algebraic topology<br />are combined in the dissertation. The axiomatic sequents of the system stem<br />from 2-cycles of &Delta;-complexes. The Euclidean and projective interpretations of<br />the sequents are defined and the decidability and soundness of the system<br />are proved. Patterns for extracting formulation and proof of the incidence<br />result from derivable sequents of system are exemplified. The procedure for<br />deciding if set of n sextuples represent an axiomatic sequent is presented<br />within the thesis.</p>

We construct and investigate random geometric structures that are based on a homogeneous Poisson point process. We investigate the random Vietoris-Rips complex constructed as the clique complex of the well known gilbert graph as an infinite random simplicial complex and prove that every realizable finite sub-complex will occur infinitely many times almost sure as isolated complex and also in the case of percolations connected to the unique giant component. Similar results are derived for the Cech complex. We derive limit theorems for the f-vector of the Vietoris-Rips complex on the unit cube centered at the origin and provide a central limit theorem and a Poisson limit theorem based on the model parameters. Finally we investigate random polytopes that are given as convex hulls of a Poisson point process in a smooth convex body. We establish a central limit theorem for certain linear combinations of intrinsic volumes. A multivariate limit theorem involving the sequence of intrinsic volumes and the number of i-dimensional faces is derived. We derive the asymptotic normality of the oracle estimator of minimal variance for estimation of the volume of a convex body.

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).