Probabilistic methods for the analysis of algorithms on random tessellations

Ross Hemsley 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Résumé : 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.
Type de document :
Thèse
Other [cs.OH]. Université Nice Sophia Antipolis, 2014. English. 〈NNT : 2014NICE4143〉
Liste complète des métadonnées

Littérature citée [114 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01099165
Contributeur : Abes Star <>
Soumis le : jeudi 9 avril 2015 - 15:34:06
Dernière modification le : samedi 27 janvier 2018 - 01:31:25
Document(s) archivé(s) le : vendredi 10 juillet 2015 - 10:36:01

Fichier

2014NICE4143.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01099165, version 2

Collections

Citation

Ross Hemsley. Probabilistic methods for the analysis of algorithms on random tessellations. Other [cs.OH]. Université Nice Sophia Antipolis, 2014. English. 〈NNT : 2014NICE4143〉. 〈tel-01099165v2〉

Partager

Métriques

Consultations de la notice

512

Téléchargements de fichiers

285