L'approximation des convexes lisses par des polytopes pour la distance de Hausdorff a connu de nombreux résultats théoriques grâce à l'apport de la géométrie riemannienne. Nous rappelons ces résultats portant principalement sur le comportement asymptotique et montrons leur utilité pour certains cas pratiques. Puis nous établissons notre résultat principal, à savoir que ce problème d'approximation d'un convexe est, en un sens bien précis, équivalent à celui de l'approximation d'une norme par une autre. Nous établissons ensuite les propriétés d'un produit d'approximations de normes, ce qui nous permet de construire par récurrence sur la dimension des polytopes approchant certains convexes lisses, ainsi que des approximations optimales des normes Lp. Enfin nous montrons à travers différentes applications à la géométrie algorithmique en quoi une approximation de norme permet de transformer un algorithme de résolution exacte en un algorithme de résolution approchée mais moins coûteux.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00005258 |
| Date | 12 December 2003 |
| Creators | Gannaz, François |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds