Étant donné un ensemble S de points du plan, une triangulation de S est une décomposition de l'enveloppe convexe de S en triangles dont les sommets sont les points de S. Une triangulation de S est dite de Delaunay si le cercle circonscrit à chaque triangle ne contient aucun point de S en son intérieur. Dans cette thèse, nous étudions une généralisation de ces notions à un ensemble S de segments disjoints du plan.<br />Nous commençons par définir une nouvelle famille de diagrammes, appelés triangulations de segments. Nous étudions leurs propriétés géométriques et topologiques et nous donnons un algorithme pour construire efficacement une telle triangulation.<br />Nous généralisons ensuite la notion de triangulation de Delaunay aux triangulations de segments et nous mettons en évidence la dualité avec le diagramme de Voronoï de segments.<br />Nous étendons également la légalité des arêtes au cas des triangulations de segments en définissant, d'une part, la légalité géométrique qui caractérise la triangulation de Delaunay de segments parmi l'ensemble de toutes les triangulations de segments possibles et, d'autre part, la légalité topologique qui caractérise les triangulations de segments qui ont la même topologie que celle de Delaunay.<br />Enfin, nous décrivons un algorithme de « flip » qui transforme toute triangulation de segments en une triangulation qui a la même topologie que celle de Delaunay. À l'aide de fonctions localement convexes, nous démontrons que la suite de triangulations construites par cet algorithme converge vers celle de Delaunay et nous prouvons qu'une triangulation de segments qui a la même topologie que celle de Delaunay est obtenue après un nombre fini d'étapes.

.

Optimization is a scientific discipline that lies at the boundary<br />between pure and applied mathematics. Indeed, while on the one hand<br />some of its developments involve rather theoretical concepts, its<br />most successful algorithms are on the other hand heavily used by<br />numerous companies to solve scheduling and design problems on a<br />daily basis.<br /><br />Our research started with the study of the conic formulation for<br />convex optimization problems. This approach was already studied in<br />the seventies but has recently gained a lot of interest due to<br />development of a new class of algorithms called interior-point<br />methods. This setting is able to exploit the two most important<br />characteristics of convexity:<br /><br />- a very rich duality theory (existence of a dual problem that is<br />strongly related to the primal problem, with a very symmetric<br />formulation),<br />- the ability to solve these problems efficiently,<br />both from the theoretical (polynomial algorithmic complexity) and<br />practical (implementations allowing the resolution of large-scale<br />problems) points of view.<br /><br />Most of the research in this area involved so-called self-dual<br />cones, where the dual problem has exactly the same structure as the<br />primal: the most famous classes of convex optimization problems<br />(linear optimization, convex quadratic optimization and semidefinite<br />optimization) belong to this category. We brought some contributions <br />in this field:<br />- a survey of interior-point methods for linear optimization, with <br />an emphasis on the fundamental principles that lie behind the design <br />of these algorithms,<br />- a computational study of a method of linear approximation of convex <br />quadratic optimization (more precisely, the second-order cone that <br />can be used in the formulation of quadratic problems is replaced by a <br />polyhedral approximation whose accuracy can be guaranteed a priori),<br />- an application of semidefinite optimization to classification, <br />whose principle consists in separating different classes of patterns <br />using ellipsoids defined in the feature space (this approach was <br />successfully applied to the prediction of student grades).<br /><br />However, our research focussed on a much less studied category of<br />convex problems which does not rely on self-dual cones, i.e.<br />structured problems whose dual is formulated very differently from<br />the primal. We studied in particular<br />- geometric optimization, developed in the late sixties, which<br />possesses numerous application in the field of engineering<br />(entropy optimization, used in information theory, also belongs to<br />this class of problems)<br />- l_p-norm optimization, a generalization of linear and convex<br />quadratic optimization, which allows the formulation of constraints<br />built around expressions of the form |ax+b|^p (where p is a fixed<br />exponent strictly greater than 1).<br /><br />For each of these classes of problems, we introduced a new type of<br />convex cone that made their formulation as standard conic problems<br />possible. This allowed us to derive very simplified proofs of the<br />classical duality results pertaining to these problems, notably weak<br />duality (a mere consequence of convexity) and the absence of a<br />duality gap (strong duality property without any constraint<br />qualification, which does not hold in the general convex case). We<br />also uncovered a very surprising result that stipulates that<br />geometric optimization can be viewed as a limit case of l_p-norm<br />optimization. Encouraged by the similarities we observed, we<br />developed a general framework that encompasses these two classes of<br />problems and unifies all the previously obtained conic formulations.<br /><br />We also brought our attention to the design of interior-point<br />methods to solve these problems. The theory of polynomial algorithms<br />for convex optimization developed by Nesterov and Nemirovski asserts<br />that the main ingredient for these methods is a computable<br />self-concordant barrier function for the corresponding cones. We<br />were able to define such a barrier function in the case of<br />l_p-norm optimization (whose parameter, which is the main<br />determining factor in the algorithmic complexity of the method, is<br />proportional to the number of variables in the formulation and<br />independent from p) as well as in the case of the general<br />framework mentioned above.<br /><br />Finally, we contributed a survey of the self-concordancy property,<br />improving some useful results about the value of the complexity<br />parameter for certain categories of barrier functions and providing<br />some insight on the reason why the most commonly adopted definition<br />for self-concordant functions is the best possible.

Dans cette thèse, nous proposons une méthode de résolution des problèmes de la géométrie algorithmique posés pour des objets courbes (par opposition aux objets "linéaires" : ensembles de points, segments, polygones ...). Les objets que nous étudions sont des courbes de Bézier composites, choisies, d'une part, pour le réalisme qu'elles assurent dans la modélisation géométrique, et d'autre part, pour la facilité du traitement algorithmique que leurs propriétés offrent. Notre approche met l'accent sur les aspects topologiques des problèmes abordés, en évitant les incohérences que la résolution en arithmétique flottante d'équations algébriques de degré élevé (générées par le traitement direct des courbes) peut le plus souvent introduire. Cet objectif est atteint par l'utilisation d'approximations polygonales convergentes, qui dans le cas des courbes de Bézier sont naturellement fournies par les polygones de controle par l'intermédiaire de la subdivision de de Casteljau. Deux des problèmes fondamentaux de la géométrie algorithmique sont traités ici, l'enveloppe convexe et les arrangements, les deux en dimension 2. Dans le cas des arrangements, la notion de topologie (combinatoire) est bien connue ; dans celui de l'enveloppe convexe, nous la définissons rigoureusement. Pour les deux problèmes, nous montrons qu'il est possible d'obtenir toute l'information topologique définissant (de manière, il est vrai, implicite, mais correcte et complète) la solution exacte en travaillant exclusivement sur les approximations polygonales des objets donnés. Les résultats théoriques obtenus sont concrétisés par des algorithmes dont la convergence et la correction sont démontrées et pour lesquels des études de cout sont réalisées. Des exemples illustrent le fonctionnement de ces algorithmes, validant la méthode proposée.

L'objectif de ce travail est d'établir l'existence et l'unicité de la solution pour une équation elliptique non linéaire dégénérée, posée dans un domaine non borné. Dans un premier temps, on mène notre étude dans un domaine borné et ceci en tronquant le domaine infini. Dans la première partie, on introduit le problème variationnel associé qui se traduit en terme d'une fonctionnelle non coercive à minimiser. Ainsi, on associe au problème de minimisation un problème dual puis on montre pour ce dernier l'existence et l'unicité de la solution. Ensuite on prouve par l'extraction d'une sous-suite minimisante l'existence d'une "solution" liée à celle du problème dual. Dans la deuxième partie, on définit un problème relaxé ayant le même infimum que le problème initial. Ensuite on établit que cet infimum est un minimum pour le problème relaxé. Les résultats de la première partie sont ensuite étendus au cas non borné. Enfin, on donne quelques critères pour estimer l'erreur de troncature entre les solutions du problème dual définies dans le cas borné et non borné.

Cette thèse porte sur deux thèmes : 1)Percolation et connexité sur les graphes géométriques aléatoires dits "type AB". 2)Comparaison stochastique directionnellement convexe de processus ponctuels et leurs propriétés de percolation et connexité. Dans le premier sujet, nous définissons un graphe biparti, dit "de type AB", sur deux processus ponctuels de Poisson indépendants. Cet graphe est une extension continue de graphe dit "type AB" sur une grille régulière. Nous montrons l'existence de percolation pour toute dimension supérieure à deux et nous établissons des bornes pour l'intensité critique. Dans le cas de dimensions deux, nous caractérisons exactement l'intensité critique. Pour le problème de connexité, nous étudions le modelé sur les processus ponctuels de Poisson indépendant dans le cube de volume un avec des intensités n et c_n pour une constante c > 0. Nous établissons des bornes asymptotiques presque sûres pour le seuil de connexité. 2) Le but du deuxième sujet de travail est de définir l'ordre directionnellement convexe de processus ponctuels est de lier cet ordre aux propriétés de regroupement des points de processus ponctuels et, dans un contexte applicatif, aux caractéristiques de la performance des réseaux de communication sans fil. La dernière partie de cette thèse porte sur la comparaison des intensités critiques de percolation pour les processus ponctuels ordonnés selon cet ordre et les applications de ces résultats de comparaison pour les réseaux sans fils. Nous concluons en montrant que les processus ponctuels inférieurs, selon cet ordre, à un processus ponctuel de Poisson ont une transition de phase non-triviale dans plusieurs modelés des percolation.

Le problème d'alignement de graphes, qui joue un rôle central dans différents domaines de la reconnaissance de formes, est l'un des plus grands défis dans le traitement de graphes. Nous proposons une méthode approximative pour l'alignement de graphes étiquetés et pondérés, basée sur la programmation convexe concave. Une application importante du problème d'alignement de graphes est l'alignement de réseaux d'interactions de protéines, qui joue un rôle central pour la recherche de voies de signalisation conservées dans l'évolution, de complexes protéiques conservés entre les espèces, et pour l'identification d'orthologues fonctionnels. Nous reformulons le problème d'alignement de réseaux d'interactions comme un problème d'alignement de graphes, et étudions comment les algorithmes existants d'alignement de graphes peuvent être utilisés pour le résoudre. Dans la formulation classique de problème d'alignement de graphes, seules les correspondances bijectives entre les noeuds de deux graphes sont considérées. Dans beaucoup d'applications, cependant, il est plus intéressant de considérer les correspondances entre des ensembles de nœuds. Nous proposons une nouvelle formulation de ce problème comme un problème d'optimisation discret, ainsi qu'un algorithme approximatif basé sur une relaxation continue. Nous présentons également deux résultats indépendants dans les domaines de la traduction automatique statistique et de la bio-informatique. Nous montrons d'une part comment le problème de la traduction statistique basé sur les phrases peut être reformulé comme un problème du voyageur de commerce. Nous proposons d'autre part une nouvelle mesure de similarité entre les sites de fixation de protéines, basée sur la comparaison 3D de nuages atomiques.

Dans la première partie de cette thèse, on présente des inégalités de concentration convexe pour des intégrales stochastiques. Ces résultats sont obtenus par calcul stochastique e tpar calcul de Malliavin forward/backward. On présente également des inégalités de déviation pour les exponentielles martingales à saut.Dans une deuxième partie on présente des théorèmes limites pour le conditionnement du mouvement brownien.

Les performances des instruments d'acquisition satellitaire progressent rapidement grâce au développement des technologies mais aussi grâce à la compréhension et l'intégration des phénomènes physiques complexes intervenant lors de l'acquisition. Cette thèse traite de plusieurs problèmes d'échantillonnage irrégulier dont les micro-vibrations des satellites dits push-broom tels que SPOT5 et les récents satellites Pléiades dont les capacités en imagerie permettent la détermination de modèles d'élévation très précis. Nous traitons aussi de l'inversion d'interferogrammes en spectrogrammétrie où l'irrégularité de l'échantillonnage est liée a la précision d'usinage des composants réfléchissants. Les micro-vibrations dans le cas du tangage sont estimées à partir d'une nappe de disparité altérée et non-dense par contraintes de parcimonie. Nous montrons expérimentalement que ce modèle et les algorithmes utilises permettent de résoudre en partie ce problème mal posé. L'ajout d'un apriori sur la régularité de l'élévation permet d'améliorer encore cette estimation dans les cas plus difficiles. Les images acquises en présence de micro-vibrations nécessitent de plus un reéchantillonnage auquel s'ajoute la déconvolution avec une problématique de coût numérique. L'algorithme que nous présentons ici répond a ces besoins grâce au cadre fonctionnel des splines que nous adaptons au problème de la déconvolution, avec des performances équivalentes a l'état de l'art et un coût numérique maîtrisé. Enfin nous abordons un problème inverse en interférométrie statique où la nature des signaux et de l'échantillonnage soulève de nombreuses questions, ce travail réalisé lors d'une R&T sur l'instrument SIFTI développé au CNES y apporte des réponses claires sous forme de résultats théoriques et numériques dans le cadre unifié des séries de Fourier non-harmoniques.

Cette thèse est constituée de deux parties indépendantes, le premier thème traitant du phénomène de concentration de la mesure pour des processus de naissance et de mort, tandis que le second est consacré aux fluctuations des intégrales stochastiques dirigées par des processus stables. <br />Dans la première partie de la thèse, nous explorons le<br />phénomène de concentration des processus de naissance et de mort. Les différentes approches considérées sont d'une part les inégalités fonctionnelles ainsi que la méthode de<br />Herbst, et d'autre part l'étude des propriétés du semigroupe associé et des techniques de martingales. En particulier, nous<br />sommes amenés à introduire diverses notions de courbures de ces processus, analogues discrets du critère de courbure de Bakry-Emery dans le cadre des processus de diffusion.<br />Dans la deuxième partie de la thèse, nous étudions le<br />comportement du processus supremum d'une intégrale stable stochastique en établissant des inégalités maximales que nous appliquons à des problèmes de temps de passage de<br />processus symétriques stables. Enfin, nous démontrons un principe de domination convexe pour des intégrales stochastiques brownienne et stable corrélées.