Algorithmes géométriques adaptatifs

Frank Nielsen 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Les travaux effectués lors de cette thèse portent sur 1a construction d'algorithmes géométriques dit adaptatifs dans 1e sens ou leur temps de calcul s'adapte a la solution construite. Nous décrivons tout d'abord les principaux paradigmes qui permettent d'obtenir des algorithmes adaptatifs. Puis , nous proposons un algorithme quasi-optimal adaptatif pour le calcul d'enveloppe convexe d'objets planaires dont la complexité de l'enveloppe convexe de toute paire soit bornée. L'algorithme est basé sur une approche composite combinant 1e paradigme mariage avant conquête et 1a méthodologie du groupement en paquets. Nous considérons également le calcul de l'enveloppe supérieure de fonctions et la décomposition convexe partielle d'un ensemble de points. Finalement, nous nous sommes intéressés aux problèmes de perçabílíté d'objets qui ont été montré NP-difficiles. En premier lieu, nous avons étudié le cas de boîtes ísothétíques en donnant une heuristique adaptative dont 1a précision soit elle-même adaptative. Ensuite, nous avons étudié les propriétés combinatoires des objets convexes pour 1a perçabílíté. Nous obtenons une batterie d'algorithmes pour des classes variées d'objets dont certains prouvent l'exístence de théorèmes de type Helly.
Type de document :
Thèse
Géométrie algorithmique [cs.CG]. Université Nice Sophia Antipolis, 1996. Français
Liste complète des métadonnées

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

https://tel.archives-ouvertes.fr/tel-00832414
Contributeur : Olivier Devillers <>
Soumis le : lundi 10 juin 2013 - 16:35:31
Dernière modification le : samedi 27 janvier 2018 - 01:30:51
Document(s) archivé(s) le : mercredi 11 septembre 2013 - 04:13:37

Identifiants

  • HAL Id : tel-00832414, version 1

Collections

Citation

Frank Nielsen. Algorithmes géométriques adaptatifs. Géométrie algorithmique [cs.CG]. Université Nice Sophia Antipolis, 1996. Français. 〈tel-00832414〉

Partager

Métriques

Consultations de la notice

1315

Téléchargements de fichiers

1006