Vers des algorithmes dynamiques randomisés en géométrie algorithmique / Monique Teillaud ; sous la direction de Jean-Daniel Boissonnat
Type 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 geometry68W20, Algorithms in computer science, Randomized algorithms
68W40, Algorithms in computer science, Analysis of algorithms
68Q25, Computer science - Theory of computing, Analysis of algorithms and problem complexity
97-02, Research exposition (monographs, survey articles) pertaining to mathematics educationNote de thèse: Thèse de doctorat, informatique, 1991, université Paris-SudEn-ligne : Tel Item type:

Current library | Call number | Status | Date due | Barcode |
---|---|---|---|---|
CMI Salle S | Thèses TEI (Browse shelf(Opens below)) | 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 on this title.