Abstract FR:

Soit s un ensemble de points pris sur une surface f d'equation z=f(x,y) ; on projette s dans le plan (xoy), et on desire construire une triangulation de l'enveloppe convexe de la projection de s qui determinera une approximation lineaire par morceaux de f, dont la qualite sera liee a une mesure de l'erreur d'approximation de la surface. Il a ete recemment prouve que la triangulation de delaunay etait optimale pour des criteres de normes lp, lorsqu'il s'agissait d'approcher lineairement toute fonction quadratique convexe, dans un espace de dimension quelconque. En revanche, tres peu de recherches ont ete menees lorsque la surface n'est pas convexe. Ce memoire propose donc d'etudier l'approximation par une triangulation, pour des criteres de normes l1 et l2, d'une surface non convexe d'equation la plus simple possible: le paraboloide hyperbolique defini par z=x2-y2. Une construction est ainsi donnee pour determiner, de maniere naturelle, les courbes de separation d'un triangle t, c'est-a-dire les limites du plan pour lesquelles t doit etre conserve dans une triangulation localement optimale du paraboloide hyperbolique. Des algorithmes de triangulation qui font appel a diverses heuristiques fondees sur les courbes de separation ont ete abondamment testes ; une amelioration significative par rapport a la triangulation de delaunay a ete mise en evidence. Une comparaison avec des triangulations globalement optimales, dont l'obtention n'est possible qu'au moyen de programmes de complexite exponentielle, prouve que ces algorithmes rendent finalement de bonnes triangulations. Les recherches montrent qu'un tel procede peut facilement etre generalise a toutes les surfaces definies par des fonctions quadratiques