Normal view MARC view ISBD view

Vers des algorithmes dynamiques randomisés en géométrie algorithmique / Monique Teillaud ; sous la direction de Jean-Daniel Boissonnat

Auteur principal : Teillaud, Monique, 1961-, AuteurAuteur secondaire : Boissonnat, Jean-Daniel, 1953-, Directeur de thèseAuteur secondaire collectivité : Université Paris-Sud, Etablissement de soutenanceType de document : ThèseLangue : français.Pays : France.Éditeur : [S.l.] : [s.n.], 1991Description : 1 vol. (178 p.) ; 30 cmISBN : 2726107184.Bibliographie : Bibliogr. p. [165]-170.Sujet MSC : 68U05, Computer science -- Computing methodologies and applications, Computer graphics; computational geometry
68W20, Computer science -- Algorithms, Randomized algorithms
68W40, Computer science -- Algorithms, Analysis of algorithms
68Q25, Computer science -- Theory of computing, Analysis of algorithms and problem complexity
97A70, Mathematics education - General, mathematics and education, Theses and postdoctoral theses
Note de thèse: Thèse de doctorat, informatique, 1991, université Paris-SudEn-ligne : Tel
Tags from this library: No tags from this library for this title. Log in to add tags.
Current location Call number Status Date due Barcode
CMI
Salle S
Thèses TEI (Browse shelf) Available 10612-01

Bibliogr. p. [165]-170

Thèse de doctorat informatique 1991 université Paris-Sud

La géométrie algorithmique a pour but de concevoir et d'analyser des algorithmes pour résoudre des problèmes géométriques. C'est un domaine récent de l'informatique théorique, qui s'est très rapidement développé depuis son apparition dans la thèse de M. I. Shamos en 1978. La randomisation permet d'éviter le recours à des structures compliquées, et s'avère très efficace, tant du point de vue de la complexité théorique, que des résultats pratiques. Nous nous sommes intéressés plus particulièrement à la conception d'algorithmes dynamiques : en pratique, il est fréquent que l'acquisition des données d'un problème soit progressive. Il n'est évidemment pas question de recalculer le résultat à chaque nouvelle donnée, d'où la nécéssité d'utiliser des schémas (semi-)dynamiques. Nous introduisons une structure très générale, le graphe d'influence, qui permet de construire de nombreuses structures géométriques : diagrammes de Voronoï, arrangements de segments... Nous étudions les algorithmes, à la fois du point de vue de la complexité théorique, de leur mise en oeuvre pratique et de l'efficacité des programmes.

There are no comments for this item.

Log in to your account to post a comment.