Complexity analysis of random convex hulls

Rémy Thomasse 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Résumé : Dans cette thèse, nous donnons de nouveaux résultats sur la taille moyenne d’enveloppes convexes de points choisis dans un convexe. Cette taille est connue lorsque les points sont choisis uniformément (et indépendamment) dans un polytope convexe, ou un convexe suffisamment «lisse» ; ou encore lorsque les points sont choisis indépendamment selon une loi normale centrée. Dans la première partie de cette thèse, nous développons une technique nous permettant de donner de nouveaux résultats lorsque les points sont choisis arbitrairement dans un convexe, puis «bruités» par une perturbation aléatoire. Ce type d’analyse, appelée analyse lissée, a initialement été développée par Spielman et Teng dans leur étude de l’algorithme du simplexe. Pour un ensemble de points arbitraires dans une boule, nous obtenons une borne inférieure et une borne supérieure de cette complexité lissée dans le cas de perturbations uniformes dans une boule en dimension arbitraire, ainsi que dans le cas de perturbations gaussiennes en dimension 2. La taille de l'enveloppe convexe de points choisis uniformément dans un convexe, peut avoir un comportement logarithmique si ce convexe est un polytope ou polynomial s’il est lisse. Nous construisons un convexe produisant un comportement oscillant entre ces deux extrêmes. Dans la dernière partie, nous présentons un algorithme pour engendrer efficacement une enveloppe convexe aléatoire de points choisis uniformément et indépendamment dans un disque sans avoir à engendrer explicitement tous les points. Il a été implémenté en C++ et intégré dans la bibliothèque CGAL.
Type de document :
Thèse
Other [cs.OH]. Université Nice Sophia Antipolis, 2015. English. 〈NNT : 2015NICE4116〉
Liste complète des métadonnées

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

https://hal.inria.fr/tel-01252937
Contributeur : Abes Star <>
Soumis le : vendredi 25 mars 2016 - 10:22:39
Dernière modification le : mercredi 10 octobre 2018 - 10:09:09

Fichier

2015NICE4116.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01252937, version 2

Citation

Rémy Thomasse. Complexity analysis of random convex hulls. Other [cs.OH]. Université Nice Sophia Antipolis, 2015. English. 〈NNT : 2015NICE4116〉. 〈tel-01252937v2〉

Partager

Métriques

Consultations de la notice

705

Téléchargements de fichiers

199