Cette thèse est une contribution à un problème classique de la géométrie algorithmique et combinatoire : l’étude des k-sets d’un ensemble V de n points du plan. Nous introduisons d’abord la notion de chaîne d’inclusion de convexes qui est un ordonnancement des points de V tel qu’aucun point n’appartient à l’enveloppe convexe de ceux qui le précèdent. Tout k-set d’une sous-suite commençante de la chaîne est appelé un k-set de la chaîne. Nous montrons que le nombre de ces k-sets est un invariant de V et qu’il est égal au nombre de régions du diagramme de Voronoï d’ordre k de V. Nous en déduisons un algorithme en ligne pour construire les k-sets des sommets d’une ligne polygonale simple dont chaque sommet est à l’extérieur de l’enveloppe convexe des sommets qui le précèdent sur la ligne. Si c est le nombre total de k-sets construits, la complexité de notrealgorithme est en O(n log n+c log^2 k) et est équivalente, par k-set construit, à celle du meilleur algorithme connu. Nous montrons ensuite que la méthode algorithmique classique de division-fusion peut être adaptée à la construction des k-sets de V. L’algorithme qui en résulte a une complexité enO(n log n+c log^2 k log(n/k)), où c est le nombre maximum de k-sets d’un ensemble de n points.Nous prouvons enfin que les centres de gravité des k-sets d’une chaîne d’inclusion de convexes sont les sommets d’une triangulation qui appartient à la même famille de triangulations, dites centroïdes, que le dual du diagramme de Voronoï d’ordre k. Nous en d´déduisons un algorithme qui construit des triangulations centroïdes particulières en temps O(n log n+k(n-k) log^2 k), ce qui est plus efficace que les algorithmes connus jusque là. / This thesis is a contribution to a classical problem in computational and combinatorial geometry: the study of the k-sets of a set V of n points in the plane. First we introduce the notion of convex inclusion chain that is an ordering of the points of V such that no point is inside the convex hull of the points that precede it. Every k-set of an initial sub-sequence of the chain is called a k-set of the chain. We prove that the number of these k-sets is an invariant of V and is equal to the number of regions in the order-k Voronoi diagram of V. We then deduce an online algorithm for the construction of the k-sets of the vertices of a simple polygonal line such that every vertex of this line is outside the convex hull of all its preceding vertices on the line. If c is the total number of k-sets built with this algorithm, the complexity of our algorithm is in O(n log n + c log^2k) and is equal, per constructed k-set, to the complexity of the best algorithm known. Afterward, we prove that the classical divide and conquer algorithmic method can be adapted to the construction of the k-sets of V. The algorithm has a complexity of O(n log n + c log^2k log(n/k)), where c is the maximum number of k-sets of a set of n points. We finally prove that the centers of gravity of the k-sets of a convex inclusion chain are the vertices of a triangulation belonging to the family of so-called centroid triangulations. This family notably contains the dual of the order-k Voronoi diagram. We give an algorithm that builds particular centroid triangulations in O(n log n + k(n- k) log^2 k) time, which is more efficient than all the currently known algorithms.

On étudie les déformations des applications harmoniques $f$ tordues par rapport à une représentation. Après avoir construit une application harmonique tordue "universelle", on donne une construction de toute déformations du premier ordre de $f$ en termes de la théorie de Hodge ; on applique ce résultat à l'espace de modules des représentations réductives d'un groupe de Kähler, pour démontrer que les points critiques de la fonctionnelle de l'énergie $E$ coïncident avec les représentations de monodromie des variations complexes de structures de Hodge. Ensuite, on procède aux déformations du second ordre, où des obstructions surviennent ; on enquête sur l'existence de ces déformations et on donne une méthode pour les construire. En appliquant ce résultat à la fonctionnelle de l'énergie comme ci-dessus, on démontre (pour n'importe quel groupe de présentation finie) que la fonctionnelle de l'énergie est strictement pluri sous-harmonique sur l'espace des modules des représentations. En assumant de plus que le groupe soit de Kähler, on étudie les valeurs propres de la matrice hessienne de $E$ aux points critiques.

Le problème abordé dans cette thèse est celui de l'existence de métriques extrémales. Si (M, J, g) est une variété kahlérienne compacte, une métrique extrémale est une métrique kählérienne dont la norme L2 de la courbure scalaire est minimale pour les métriques représentant la même classe de Kähler. On propose de nouvelles constructions de métriques extrémales utilisant des méthodes perturbatives. Dans un premier temps, on montre que si (M, J, g) est une surface orbifold extrémale qui ne possède que des singularités isolées de type Hirzebruch-Jung, alors une résolution de (M, J) admet une métrique extrémale. On donne des applications de ce résultat sur l'existence de métriques extrémales sur les éclatements de surfaces réglées paraboliques. Dans une seconde partie, on etudie la stabilié des métriques extrémales sous déformations complexes. Ceci est un travail réalisé en collaboration avec Yann Rollin et Santiago Simanca. On donne un critère suffisant pour assurer la stabilité d'une métrique extrémale lors d'une déformation complexe munie d'une action holomorphe d'un groupe compact. On généralise ainsi des résultats de S.Simanca et C.Lebrun. Ceci nous permet également de retrouver un résultat de S.Donaldson, a savoir une métrique Kähler-Einstein sur une déformation de la variété de Mukai et Umemura.

Introduite par B. Totaro, la filtration par le poids sur l'homologie des variétés algébriques réelles, analogue réel de la filtration par le poids de P. Deligne sur les variétés algébriques complexes, a été réalisée via un complexe de chaînes filtré par C. McCrory et A. Parusinski, qui en ont enrichi la compréhension, notamment à travers l'étude de la suite spectrale induite. Au milieu des nombreuses informations recelées par cette suite spectrale de poids, on retrouve les nombres de Betti virtuels. Dans cette thèse, on montre l'existence d'une filtration par le poids équivariante sur l'homologie équivariante des variétés algébriques réelles munies d'une action d'un groupe fini. On la réalise par un complexe filtré et, via la construction de plusieurs suites spectrales, on effectue des avancées significatives pour extraire des invariants additifs. Lors de notre étude, on définit fonctoriellement un complexe de poids avec action et on montre qu'un résultat de découpage d'une variété Nash munie d'une involution algébrique entraîne un analogue de la suite exacte de Smith, tenant compte de la filtration Nash-constructible. A travers la construction d'un complexe de poids invariant dans le cadre d'involutions algébriques, on retrouve également les nombres de Betti virtuels équivariants de G. Fichou. Enfin, en appliquant les bons foncteurs aux résultats sur les produits de filtrations par le poids réelles de T. Limoges, on donne des résultats sur les produits de filtrations par le poids équivariantes.

Cette thèse s'intéresse aux automorphismes des surfaces algébriques réelles, c'est-à-dire les transformations polynomiales admettant un inverse polynomial. La question centrale est de savoir si leur restriction au lieu réel reflète toute la richesse de la dynamique complexe. Celle-ci est traitée sous deux aspects : celui de l'entropie topologique et celui de l'ensemble de Fatou. Pour le premier point, on introduit une quantité purement géométrique, appelée concordance, qui ne dépend que de la surface. Puis on montre que le rapport des entropies réelle et complexe est relié à cette quantité. La concordance est calculée explicitement sur de nombreux exemples de surfaces, notamment les surfaces abéliennes qui sont traitées en détails, ainsi que certaines surfaces K3. Dans la seconde partie, on étudie l'ensemble de Fatou, qui correspond aux pointscomplexes pour lesquels la dynamique est simple. On montre, grâce à des résultats antérieurs de Dinh et Sibony sur les courants positifs fermés, que celui-ci est hyperbolique au sens de Kobayashi, quitte à lui enlever certaines courbes fixées par (unitéré de) notre transformation. Cette propriété permet d'en déduire que ce lieu réel ne peut pas être entièrement contenu dans l'ensemble de Fatou, hormis quelques cas exceptionnels où la topologie du lieu réel est simple et la dynamique bien comprise. Ainsi la complexité de la dynamique est presque toujours observable sur les points réels.

La recherche d'une compactification de l'ensemble des métriques Riemanniennes à singularités coniques sur une surface amène naturellement à l'étude des "surfaces à Courbure Intégrale Bornée au sens d'Alexandrov". Il s'agit d'une géométrie singulière, développée par A. Alexandrov et l'école de Leningrad dans les années 1970, et dont la caractéristique principale est de posséder une notion naturelle de courbure, qui est une mesure. Cette large classe géométrique contient toutes les surfaces "raisonnables" que l'on peut imaginer.Le résultat principal de cette thèse est un théorème de compacité pour des métriques d'Alexandrov sur une surface ; un corollaire immédiat concerne les métriques Riemanniennes à singularités coniques. On décrit dans ce manuscrit trois hypothèses adaptées aux surfaces d'Alexandrov, à la manière du théorème de compacité de Cheeger-Gromov qui concerne les variétés Riemanniennes à courbure bornée, rayon d'injectivité minoré et volume majoré. On introduit notamment la notion de rayon de contractibilité, qui joue le rôle du rayon d'injectivité dans ce cadre singulier.On s'est également attachés à étudier l'espace (de module) des métriques d'Alexandrov sur la sphère, à courbure positive le long d'une courbe fermée. Un sous-ensemble intéressant est constitué des convexes compacts du plan, recollés le long de leurs bords. A la manière de W. Thurston, C. Bavard et E. Ghys, qui ont considéré l'espace de module des polyèdres et polygones (convexes) à angles fixés, on montre que l'identification d'un convexe à sa fonction de support fait naturellement apparaître une géométrie hyperbolique de dimension infinie, dont on étudie les premières propriétés. / If we look for a compactification of the space of Riemannian metrics with conical singularities on a surface, we are naturally led to study the "surfaces with Bounded Integral Curvature in the Alexandrov sense". It is a singular geometry, developed by A. Alexandrov and the Leningrad's school in the 70's, and whose main feature is to have a natural notion of curvature, which is a measure. This large geometric class contains any "reasonable" surface we may imagine.The main result of this thesis is a compactness theorem for Alexandrov metrics on a surface ; a straightforward corollary concerns Riemannian metrics with conical singularities. We describe here three hypothesis which pair with the Alexandrov surfaces, following Cheeger-Gromov's compactness theorem, which deals with Riemannian manifolds with bounded curvature, injectivity radius bounded by below and volume bounded by above. Among other things, we introduce the new notion of contractibility radius, which plays the role of the injectivity radius in this singular setting.We also study the (moduli) space of Alexandrov metrics on the sphere, with non-negative curvature along a closed curve. An interesting subset is the set of compact convex sets, glued along their boundaries. Following W. Thurston, C. Bavard and E. Ghys, who considered the moduli space of (convex) polyhedra and polygons with fixed angles, we show that the identification between a convex set and its support function give rise to an infinite dimensional hyperbolic geometry, for which we study the first properties.

Représenter un objet géométrique complexe par un ensemble de primitives simples est une tâche souvent fondamentale, que ce soit pour la reconstruction et la réparation de données, ou encore pour faciliter la visualisation ou la manipulation des données. Le choix de la ou les primitives, ainsi que celui de la méthode d'approximation, impactent fortement les propriétés de la représentation de forme qui sera obtenue.Dans cette thèse, nous utilisons les boules comme seule primitive. Nous prenons ainsi un grand soin à décrire les unions finies de boules et leur structure. Pour cela, nous nous reposons sur les faisceaux de boules. En particulier, nous aboutissons à une description valide en toute dimension, sans hypothèse de position générale. En chemin, nous obtenons également plusieurs résultats portant sur les tests d'inclusion locale et globale dans une union de boules.Nous proposons également une nouvelle méthode d'approximation par union finie de boules, l'approximation par boules à (delta,epsilon)-près. Cette approche contraint l'union de boules à couvrir un sous-ensemble de la forme d'origine (précisément, un epsilon-érodé), tout en étant contenu dans un sur-ensemble de la forme (un delta-dilaté). En nous appuyant sur nos précédents résultats portant sur les unions de boules, nous démontrons plusieurs propriétés de ces approximations. Nous verrons ainsi que calculer une approximation par boules à (delta,epsilon)-près qui soit de cardinal minimum est un problème NP-complet. Pour des formes simples dans le plan, nous présentons un algorithme polynomial en temps et en espace qui permet de calculer ces approximations de cardinal minimum. Nous concluons par une généralisation de notre méthode d'approximation pour une plus large variété de sous-ensembles et sur-ensembles. / Describing a complex geometric shape with a set of simple primitives is often a fundamental task for shape reconstruction, visualization, analysis and manipulation. The type of primitives, as well as the choice of approximation scheme, both greatly impact the properties of the resulting shape representation.In this PhD, we focus on balls as primitives. Using pencils of balls, we carefully describe finite unions of balls and their structure. In particular, our description holds in all dimension without assuming general position. On our way, we also establish various results and tools to test local and global inclusions within these unions.We also propose a new approximation scheme by union of balls, the (delta,epsilon)-ball approximation. This scheme constrains the approximation to cover a core subset of the original shape (specifically, an epsilon-erosion), while being contained within a superset of the shape (a delta-dilation). Using our earlier results regarding finite unions of balls, we prove several properties of these approximations. We show that computing a cardinal minimum (delta,epsilon)-ball approximation is an NP-complete problem. For simple planar shapes however, we present a polynomial time and space algorithm that outputs a cardinal minimum approximation. We then conclude by generalizing the approximation scheme to a wider range of core subsets and bounding supersets.

L'étude des espaces-temps plats singuliers munis d'une surface de Cauchy polyédrale est motivée par leur rôle de model jouet de gravité quantique proposé par Deser, Jackiw et 'T Hooft. Cette thèse porte sur les paramétrisations de certaines classes d'espaces-temps plat singuliers : les espaces-temps plats avec particules massives et BTZ Cauchy-compacts maximaux. Deux paramétrisations sont proposées, l'une reposant sur une extension du théorème de Mess aux espaces-temps plats avec BTZ et la surface de Penner-Epstein, l'autre reposant sur une généralisation du théorème d'Alexandrov aux espaces-temps plats avec particules massives et BTZ. Ce travail propose également une amorce de cadre théorique permettant de considérer des espaces-temps singuliers plus généraux. / The study of singular flat spacetimes with polyhedral Cauchy-surfaces is motivated by the quantum gravity toy model role they play in the seminal work of Deser, Jackiw and 'T Hooft. This thesis study parametrisations of classes of singular flat spacetimes : Cauchy-compact maximal flat spacetimes with massive and BTZ-like singularities. Two parametrisations are constructed. The first is based on an extension of Mess theorem to flat spacetimes with BTZ and Penner-Epstein convex hull construction. The second is based on a generalisation of Alexandrov polyhedron theorem to radiant Cauchy-compact flat spacetimes with massive and BTZ-like singularities. This work also initiate a wider theoretical background that encompass singular spacetimes.

No description available.

Pour d non puissance d’un nombre premier, le nombre maximal de bases deux à deux décorrélées d’un espace de Hilbert de dimension d n’est pas encore connu. Dans ce mémoire, nous commençons par donner une construction de bases décorrélées en lien avec une famille de représentations irréductibles de l'algèbre de Lie su(2) et faisant appel aux sommes de Gauss.Puis nous étudions de façon systématique la possibilité de construire de telle bases au moyen des opérateurs de Pauli. 1) L’étude de la droite projective sur Zdm montre que, pour obtenir des ensembles maximaux de bases décorrélées à l’aide d'opérateurs de Pauli, il est nécessaire de considérer des produits tensoriels de ces opérateurs. 2) Les sous-modules lagrangiens de Zd2n, dont nous donnons une classification complète, rendent compte des ensembles maximalement commutant d'opérateurs de Pauli. Cette classification permet de savoir lesquels de ces ensembles sont susceptibles de donner des bases décorrélées : ils correspondent aux demi-modules lagrangiens, qui s'interprètent encore comme les points isotropes de la droite projective (P(Mat(n, Zd)²),ω). Nous explicitons alors un isomorphisme entre les bases décorrélées ainsi obtenues et les demi-modules lagrangiens distants, ce qui précise aussi la correspondance entre sommes de Gauss et bases décorrélées. 3) Des corollaires sur le groupe de Clifford et l’espace des phases discret sont alors développés.Enfin, nous présentons quelques outils inspirés de l’étude précédente. Nous traitons ainsi du rapport anharmonique sur la sphère de Bloch, de géométrie projective en dimension supérieure, des opérateurs de Pauli continus et nous comparons l'entropie de von Neumann à une mesure de l'intrication par calcul d'un déterminant. / For d not a power of a prime, the maximal number of mutually unbiased bases (MUBs) in a d-dimensional Hilbert space is still unknown. In this thesis, we begin by an original building of MUBs by means of Gauss sums, in relation with a family of irreducible representations of the Lie algebra su(2).Then, we sytematically study the possibility of building such bases by means of Pauli operators. 1) The study of the projective line on Zdm shows that, in order to obtain maximal sets of MUBs, tensorial products of these operators are in order. 2) Lagrangian submodules of Zd2n, of which we give a complete classification, account for maximally commuting sets of Pauli operators. This classification enables to know which of these sets are likely to yield unbiased bases. They correspond to Lagrangian half-modules that can be interpreted as the isotropic points of the projective line (P(Mat(n, Zd)²),ω). Hence, we establish an isomorphism between the unbiased bases thus obtained and distant Lagrangian half-modules, which precises by the way the correspondance between Gauss sums and MUBs. 3) Corollaries on the Clifford group and the finite phase space are then developed.Finally, we present some tools inspired by the previous study. We deal with the cross-ratio on the Bloch sphere and projective geometry in higher dimension, Pauli operators with continuous exponents and we compare von Neumann entropy with a determinantal measure of entanglement