Dans cette thèse, nous exploitons les outils de la théorie des probabilités et de la géométrie stochastique pour analyser des algorithmes opérant sur les tessellations. Ce travail est divisé entre deux thèmes principaux, le premier traite de la navigation dans une tessellation de Delaunay et dans son dual, le diagramme de Voronoï avec des implications pour les algorithmes de localisation spatiales et de routage dans les réseaux en ligne. Nous proposons deux nouveaux algorithmes de navigation dans la triangulation de Delaunay, que nous appelons Pivot Walk et Cone Walk. Pour Cone Walk, nous fournissons une analyse en moyenne détaillée avec des bornes explicites sur les propriétés de la pire marche possible effectuée par l'algorithme sur une triangulation de Delaunay aléatoire d'une région convexe bornée. C'est un progrès significatif car dans l'algorithme Cone Walk, les probabilités d'utiliser un triangle ou un autre au cours de la marche présentent des dépendances complexes, dépendances inexistantes dans d'autres marches. La deuxième partie de ce travail concerne l'étude des propriétés extrémales de tessellations aléatoires. En particulier, nous dérivons les premiers et derniers statistiques d'ordre pour les boules inscrites dans les cellules d'un arrangement de droites Poissonnien; ce résultat a des implications par exemple pour le hachage respectant la localité. Comme corollaire, nous montrons que les cellules minimisant l'aire sont des triangles. / In this thesis, we leverage the tools of probability theory and stochastic geometry to investigate the behavior of algorithms on geometric tessellations of space. This work is split between two main themes, the first of which is focused on the problem of navigating the Delaunay tessellation and its geometric dual, the Voronoi diagram. We explore the applications of this problem to point location using walking algorithms and the study of online routing in networks. We then propose and investigate two new algorithms which navigate the Delaunay triangulation, which we call Pivot Walk and Cone Walk. For Cone Walk, we provide a detailed average-case analysis, giving explicit bounds on the properties of the worst possible path taken by the algorithm on a random Delaunay triangulation in a bounded convex region. This analysis is a significant departure from similar results that have been obtained, due to the difficulty of dealing with the complex dependence structure of localized navigation algorithms on the Delaunay triangulation. The second part of this work is concerned with the study of extremal properties of random tessellations. In particular, we derive the first and last order-statistics for the inballs of the cells in a Poisson line tessellation. This result has implications for algorithms involving line tessellations, such as locality sensitive hashing. As a corollary, we show that the cells minimizing the area are triangles.

Aujourd'hui, les véhicules sont devenus de plus en plus sophistiqués, intelligents et connectés. En effet, ils sont équipés de capteurs, radars, GPS, interfaces de communication et capacités de traitement et de stockage élevés. Ils peuvent collecter, traiter et communiquer les informations relatives à leurs conditions de travail et leur environnement formant un réseau véhiculaire. L'intégration des technologies de communication sur les véhicules fait l'objet d'une immense attention de l'industrie, des autorités gouvernementales et des organisations de standardisations; elle a ouvert la voie à des applications innovantes qui vont révolutionner le marché de l'automobile avec les principaux objectifs d'assurer la sécurité sur les routes, augmenter l'efficacité des transports et offrir un confort aux conducteurs et passagers. En outre, le transport est un secteur en évolution active. Des moyens de transport plus durables comme les véhicules électriques s'introduisent progressivement sur le marché de l'automobile tout en créant de nouveaux défis liés à la contrainte énergétique et la protection de l'environnement qui restent à résoudre.De nombreux projets et études ont été initiés exploitant les avantages des technologies de l'information et de communication (TIC) afin de répondre aux différents défis des systèmes de transport. Cependant, avoir des véhicules connectés et coopératifs crée un réseau hautement dynamique caractérisé par des ruptures de lien et de pertes de messages très fréquentes. Pour résoudre ces problèmes de communication, cette thèse se concentre sur deux axes majeurs: (i) le véhicule connecté (ou mobilité connectée) et (ii) la mobilité durable. Dans la première partie de cette thèse, la diffusion, la collecte et l'acheminement de données dans un réseau de véhicule sont adressés. Ainsi, un nouveau protocole de diffusion est proposé afin de faire face à la fragmentation et la connectivité intermittente dans ces réseaux. Ensuite, une nouvelle stratégie de déploiement d'infrastructure de communication est conçue afin d'améliorer la connectivité réseau et l'utilisation des ressources. Enfin, un nouveau protocole de routage, pour applications sensibles au délai, utilisant cette nouvelle infrastructure de communication est proposé. La deuxième partie se concentre sur la mobilité durable avec un focus sur les véhicules électriques et avec un objectif de réduire les problèmes de pollution et d'utiliser efficacement l'énergie. Une nouvelle architecture de gestion de flottes de véhicules électriques est proposée. Cette dernière utilise les protocoles implémentés dans la première partie de cette thèse afin de collecter, traiter et diffuser les données. Elle permet de surmonter les limitations liées à la courte autonomie des batteries des véhicules électriques. Ensuite, pour répondre aux besoins et défis d'équilibre énergétique, un nouveau schéma de déploiement des stations de recharge pour véhicules électriques est proposé. Cette solution permet de satisfaire les demandes des conducteurs en terme d'énergie, tout en tenant compte les capacités énergétiques disponibles. / Today, vehicles have become more sophisticated, intelligent and connected. Indeed, they are equipped with sensors, radars, GPS, communication interfaces and high processing and storage capacities. They can collect, process and communicate information related to their working conditions and their environment forming a vehicular network. The incorporation of communication technologies on vehicles garnered a huge attention of industry, government authorities and standardizations organizations and opened the way for innovative applications that revolutionized the automotive market with the main goals to ensure safety on roads, increase transport efficiency and provide comfort to drivers and passengers. In addition, transportation is still an actively evolving sector. More sustainable means of transportation such as electric vehicles are introduced progressively to the automotive market with new challenges related to energy consumption and environment preservation that remain to be solved. Many research investigations and industrial projects are done to exploit the advantages of information and communication technologies (ICT) to fit with transportation challenges. However, having connected and cooperative vehicles creates a highly dynamic network characterized by frequent link breaks and message losses. To cope with these communication limitations, this thesis focuses on two major axis: (i) connected vehicle or connected mobility and (ii) sustainable mobility. In the first part of this thesis, data dissemination, collection and routing in vehicular networks are addressed. Thus, a new dissemination protocol is proposed to deal with frequent network fragmentation and intermittent connectivity in these networks. Then, a new deployment strategy of new communication infrastructure is developed in order to increase network connectivity and enhance the utilization of the network resources. Finally, a new routing protocol, for delay-sensitive applications, that uses the optimized infrastructure deployment is proposed. The second part focuses on sustainable mobility with a focus on electric vehicles and with the main objective is to reduce pollution issues and make better use of energy. A new architecture for electric vehicles fleet management is proposed. This latter uses the implemented protocols of the first part of this thesis in order to collect, process and disseminate data. It helps to overcome the limitations related to short autonomy of electric vehicles. Then, to meet energy balance challenges, a new deployment scheme for electric vehicles charging stations is developed. This solution helps to satisfy drivers’ demands in term of energy while taking into account available resources.