En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c'est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s'avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s'agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d'autre d'une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l'épaisseur d'un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure

Le problème de Lehmer consiste à minorer la hauteur de Weil d'un nombre algébrique en fonction de son degré sur Q. Si la question originelle de Lehmer reste aujourd'hui sans réponse, la conjecture optimale correspondante a été démontrée à un epsilon près. Par ailleurs, ce problème admet plusieurs généralisations. D'une part, on peut formuler le même type de conjecture en remplaçant le corps des rationnels par une extension abélienne d'un corps de nombres. D'autre part, on peut généraliser ces énoncés en dimension supérieure. Il s'agit alors de minorer la hauteur normalisée d'un point ou d'une sous-variété d'un tore ; dans ce cas, on substitue au degré un invariant plus fin : l'indice d'obstruction. Il est ensuite naturel de chercher à combiner ces deux généralisations : c'est le problème de Lehmer relatif dans un tore.<br /><br />Dans cette thèse, nous considérons tout d'abord le problème de Lehmer relatif unidimensionnel. Nous donnons une minoration pour la hauteur d'un nombre algébrique en fonction de son degré sur une extension abélienne d'un corps de nombres. Il s'agit d'une amélioration d'un théorème d'Amoroso et Zannier, obtenue à l'aide d'une démonstration techniquement plus simple. De plus, nous explicitons la dépendance de la borne inférieure en le corps de base. Puis nous abordons le problème de Lehmer relatif en dimension supérieure et minorons la hauteur d'une hypersurface en fonction de son indice d'obstruction sur une extension abélienne de Q. Enfin, nous obtenons un résultat analogue pour un point, sous réserve que celui-ci satisfasse une hypothèse technique. Nous montrons ainsi les conjectures les plus fines à un epsilon près.

Cette thèse concerne le problème de trouver une notion naturelle de «courbure scalaire» en géométrie kählérienne généralisée. L'approche utilisée consiste à calculer l'application moment pour l'action du groupe des difféomorphismes hamiltoniens sur l'espace des structures kählériennes généralisées de type symplectique. En effet, il est bien connu que l'application moment pour la restriction de cette action aux structures kählériennes s'identifie à la courbure scalaire riemannienne. On se limite à une certaine classe de structure kählériennes généralisées sur les variétés toriques notée $DGK_{\omega}^{\mathbb{T}}(M)$ que l'on reconnaît comme étant classifiées par la donnée d'une matrice antisymétrique $C$ et d'une fonction réelle strictement convexe $\tau$ (ayant un comportement adéquat au voisinage de la frontière du polytope moment). Ce point de vue rend évident le fait que toute structure kählérienne torique peut être déformée en un élément non kählérien de $DGK_{\omega}^{\mathbb{T}}(M)$, et on note que cette déformation à lieu le long d'une des classes que R. Goto a démontré comme étant libre d'obstruction. On identifie des conditions suffisantes sur une paire $(\tau,C)$ pour qu'elle donne lieu à un élément de $DGK_{\omega}^{\mathbb{T}}(M)$ et on montre qu'en dimension 4, ces conditions sont également nécessaires. Suivant l'adage «l'application moment est la courbure» mentionné ci-haut, des formules pour des notions de «courbure scalaire hermitienne généralisée» et de «courbure scalaire riemannienne généralisée» (en dimension 4) sont obtenues en termes de la fonction $\tau$. Enfin, une expression de la courbure scalaire riemannienne généralisée en termes de la structure bihermitienne sous-jacente est dégagée en dimension 4. Lorsque comparée avec le résultat des physiciens Coimbra et al., notre formule suggère un choix canonique pour le dilaton de leur théorie. / This thesis is about the problem of finding a natural notion of "scalar curvature" in generalized Kähler geometry. The approach taken here is to compute the moment map for the action of the group of hamiltonian diffeomorphisms on the space of generalized Kähler structures of symplectic type. Indeed, it is well known that the moment map for the restriction of this action to the space of ordinary Kähler structures can be naturally identified with the riemannian scalar curvature. We concern ourselves only with a certain class of generalized Kähler structures on toric manifolds which we denote by $DGK_{\omega}^{\mathbb{T}}(M)$ and which we recognize as being classified by the data of an antisymetric matrix $C$ and a real-valued strictly convex functions $\tau$ (exhibiting appropriate behavior on a neighborhood of the boundary of the moment polytope). This viewpoint makes obvious the fact that any toric Kähler structure can be deformed to a non-Kähler element of $DGK_{\omega}^{\mathbb{T}}(M)$, and we note that this deformation happens along one of the classes which were shown by R. Goto to be unobstructed. We identify sufficient conditions on a pair $(\tau,C)$ for it to define an element of $DGK_{\omega}^{\mathbb{T}}(M)$ and we show that in dimension 4, these conditions are also necessary. Following the adage "the moment map is the curvature" mentioned above, formulas for notions of "generalized Hermitian scalar curvature" and "generalized Riemannian scalar curvature" (in dimension 4) are obtained in terms of the function $\tau$. Finally, an expression for the generalized Riemannian scalar curvature in terms of the underlying bi-Hermitian structure is found in dimension 4. When compared with the results of the physicists Coimbra et al., our formula suggests a canonical choice for the dilaton of their theory.

La problématique centrale de cette thèse est l'élaboration d'un opérateur de Laplace--Beltrami discret sur les surfaces digitales. Ces surfaces proviennent de la théorie de la géométrie discrète, c’est-à-dire la géométrie qui s'intéresse à des sous-ensembles des entiers relatifs. Nous nous plaçons ici dans un cadre théorique où les surfaces digitales sont le résultat d'une approximation, ou processus de discrétisation, d'une surface continue sous-jacente. Cette méthode permet à la fois de prouver des théorèmes de convergence des quantités discrètes vers les quantités continues, mais aussi, par des analyses numériques, de confirmer expérimentalement ces résultats. Pour la discrétisation de l’opérateur, nous faisons face à deux problèmes : d'un côté, notre surface n'est qu'une approximation de la surface continue sous-jacente, et de l'autre côté, l'estimation triviale de quantités géométriques sur la surface digitale ne nous apporte pas en général une bonne estimation de cette quantité. Nous possédons déjà des réponses au second problème : ces dernières années, de nombreux articles se sont attachés à développer des méthodes pour approximer certaines quantités géométriques sur les surfaces digitales (comme par exemple les normales ou bien la courbure), méthodes que nous décrirons dans cette thèse. Ces nouvelles techniques d'approximation nous permettent d'injecter des informations de mesure sur les éléments de notre surface. Nous utilisons donc l'estimation de normales pour répondre au premier problème, qui nous permet en fait d'approximer de façon précise le plan tangent en un point de la surface et, via une méthode d'intégration, palier à des problèmes topologiques liées à la surface discrète. Nous présentons un résultat théorique de convergence du nouvel opérateur discrétisé, puis nous illustrons ensuite ses propriétés à l’aide d’une analyse numérique de l’opérateur. Nous effectuons une comparaison détaillée du nouvel opérateur par rapport à ceux de la littérature adaptés sur les surfaces digitales, ce qui nous permet, au moins pour la convergence, de montrer que seul notre opérateur possède cette propriété. Nous illustrons également l’opérateur via quelques unes de ces applications comme sa décomposition spectrale ou bien encore le flot de courbure moyenne / The central issue of this thesis is the development of a discrete Laplace--Beltrami operator on digital surfaces. These surfaces come from the theory of discrete geometry, i.e. geometry that focuses on subsets of relative integers. We place ourselves here in a theoretical framework where digital surfaces are the result of an approximation, or discretization process, of an underlying smooth surface. This method makes it possible both to prove theorems of convergence of discrete quantities towards continuous quantities, but also, through numerical analyses, to experimentally confirm these results. For the discretization of the operator, we face two problems: on the one hand, our surface is only an approximation of the underlying continuous surface, and on the other hand, the trivial estimation of geometric quantities on the digital surface does not generally give us a good estimate of this quantity. We already have answers to the second problem: in recent years, many articles have focused on developing methods to approximate certain geometric quantities on digital surfaces (such as normals or curvature), methods that we will describe in this thesis. These new approximation techniques allow us to inject measurement information into the elements of our surface. We therefore use the estimation of normals to answer the first problem, which in fact allows us to accurately approximate the tangent plane at a point on the surface and, through an integration method, to overcome topological problems related to the discrete surface. We present a theoretical convergence result of the discretized new operator, then we illustrate its properties using a numerical analysis of it. We carry out a detailed comparison of the new operator with those in the literature adapted on digital surfaces, which allows, at least for convergence, to show that only our operator has this property. We also illustrate the operator via some of these applications such as its spectral decomposition or the mean curvature flow

Dans cette thèse des actions conformes de cohomogénéité un sur l'univers d'Einstein tridimensionel sont classifiées. Notre stratégie est d'établir dans un premier temps quel peut être le groupe de transformations conformes impliqué, à conjugaison près. Nous décrivons aussi la topologie et la nature causale des orbites d'une telle action. / In this thesis, the conformal actions of cohomogeneity one on the three-dimensional Einstein universe are classified. Our strategy in this study is to determine the representation of the acting group in the group of conformal transformations of Einstein universe up to conjugacy. Also, we describe the topology and the causal character of the orbits induced by cohomogeneity one actions in Einstein universe.

Convex geometries are combinatorial structures; they capture in an abstract way the essential features of convexity in Euclidean space, graphs or posets for instance. A convex geometry consists of a finite ground set plus a collection of subsets, called the convex sets and satisfying certain axioms. In this work, we study two natural problems on convex geometries. First, we consider the maximum-weight convex set problem. After proving a hardness result for the problem, we study a special family of convex geometries built on split graphs. We show that the convex sets of such a convex geometry relate to poset convex geometries constructed from the split graph. We discuss a few consequences, obtaining a simple polynomial-time algorithm to solve the problem on split graphs. Next, we generalize those results and design the first polynomial-time algorithm for the maximum-weight convex set problem in chordal graphs. Second, we consider the realizability problem. We show that deciding if a given convex geometry (encoded by its copoints) results from a point set in the plane is ER-hard. We complete our text with a brief discussion of potential further work. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Ce mémoire d'habilitation à diriger des recherches est constitué des deux parties: - la première partie revient sur les idées et les concepts de la géométrie non commutative. Le point central de cet exposé est de rappeler les résultats qui motivent les recherches en géométrie non commutative, au sens où ces résultats donnent un sens à la démarche promue par la géométrie non commutative. Ces résultats sont bien connus désormais, et ils s'articulent autour de constructions pouvant prendre sens à la fois dans un cadre topologique et/ou géométrique et dans un cadre plus algébrique. Ainsi on trouvera le théorème de Gelfand-Naïmark sur les C*-algèbres commutatives, des rappels sur la K-théorie, d'abord pour les espaces topologiques, puis pour les C*-algèbres, une introduction à la cohomologie cyclique en insistant sur ses liens avec les structures différentiables, finalement un exposé sur l'objet "magique" qui connecte entre eux tous ces domaines, à la fois dans le cadre purement topologique, dans le cadre de la géométrie différentielle, et enfin dans le cadre algébriques : le caractère de Chern. - la seconde partie est une revue qui fait le point sur l'état des recherches sur la géométrie non commutative de l'algèbre des endomorphismes d'un fibré vectoriel de groupe de structure SU(n), en donnant si possible toutes les définitions utiles, de façon à faire un texte relativement autonome. Plus encore, il s'agit de montrer en quoi cette géométrie étend de façon naturelle la géométrie ordinaire du fibré principal sous-jacent, et en quoi les résultats obtenus sur les liens entre les connexions ordinaires et les connexions non commutatives dans ce contexte sont une excellente généralisation de la notion ordinaire de connexion. C'est pourquoi, dans cet exposé, sont rappelés les concepts usuels des théories de jauge ordinaires, et sont décrits très précisément où et comment la nouvelle géométrie se greffe à ces concepts. En particulier, il est insisté sur le fait que la notion de connexion prend un sens dans un niveau "intermédiaire", entre sa définition comme forme globale sur le fibré principal et sa définition comme familles de formes locales sur la variété de base satisfaisant à des recollements non homogènes. Le niveau intermédiaire utilise la géométrie de nature non commutative de l'algèbre des endomorphismes, et correspond à un regard nouveau sur les concepts usuels manipulés dans le cadre des théories de jauge.

Sur l'ensemble des variétés riemanniennes compactes à courbure de Ricci positive (on normalise par $Ric \geq (n-1)g$), la première valeur propre non nulle du laplacien agissant sur les fonctions atteint son minimum uniquement pour la sphère canonique. Dans cette thèse, nous caractérisons, à l'aide de la distance de Gromov-Hausdorff, les variétés riemanniennes à courbure positive dont les premières valeurs propres du laplacien sont proches de celles de la sphère canonique. Cette propriété de minimimalité du spectre de la sphère s'étend par un procédé de symétrisation, au spectre de Dirichlet des boules géodésiques de la sphère parmi les domaines de variétés à courbure de Ricci positive. Nous étudions les domaines de variétés à courbure de Ricci positive dont la première valeur propre de Dirichlet est presque minimimale. En particulier, nous montrons qu'un domaine convexe dont la première valeur propre de Dirichlet est proche de celle d'un hémisphèere est Gromov-Hausdorff proche d'un hémisphère d'un sinus produit tordu.

L'approximation des convexes lisses par des polytopes pour la distance de Hausdorff a connu de nombreux résultats théoriques grâce à l'apport de la géométrie riemannienne. Nous rappelons ces résultats portant principalement sur le comportement asymptotique et montrons leur utilité pour certains cas pratiques. Puis nous établissons notre résultat principal, à savoir que ce problème d'approximation d'un convexe est, en un sens bien précis, équivalent à celui de l'approximation d'une norme par une autre. Nous établissons ensuite les propriétés d'un produit d'approximations de normes, ce qui nous permet de construire par récurrence sur la dimension des polytopes approchant certains convexes lisses, ainsi que des approximations optimales des normes Lp. Enfin nous montrons à travers différentes applications à la géométrie algorithmique en quoi une approximation de norme permet de transformer un algorithme de résolution exacte en un algorithme de résolution approchée mais moins coûteux.

Cette thèse propose une notion de quantification par déformation des variétés de Poisson au sens des C*-algèbres, en lien notamment avec l'emploi de groupoïdes. Cette théorie s'appuie sur des exemples, notamment celui des variétés toriques. La première partie est un rappel de connaissances développées depuis quelques dizaines d'années sur les groupoïdes et leurs C*-algèbres. La deuxième partie présente les définitions de déformation et de quantification utilisées ensuite, et leur traduction, pour les groupoïdes, dans la notion importante de groupoïde de déformation. Une large classe de sous-groupoïdes des groupoïdes de Lie est de ce type. Enfin le résultat principal de cette thèse est une condition suffisante sur les variétés M munies de l'action d'un tore Tn pour construire un groupoïde de déformation associé, au moyen du choix d'une action de Rn sur une variété contenant le quotient M/Tn ; ce groupoïde se présente comme un sous-groupoïde du groupoïde de l'action d'un groupe discret. On retrouve alors des résultats de quantification connus pour Cn, les tores et les sphères de dimension 4 non commutatifs. La troisième partie applique ce résultat à l'exemple des variétés toriques, dont la géométrie étonnante, en terme de moment notamment, fut découverte dans les années 80. Cette construction fournit le premier exemple de quantification des variétés toriques dans un cadre C*-algebrique, même dans les cas les plus simples (sphère de dimension 2, espaces projectifs complexes).