les années 1990 et a conduit à des analyses
précises, validées expérimentalement. Dans
bien des cas, et le calcul de la triangulation
de Delaunay en est un, l’introduction d’une
part de hasard autorise à ne pas chercher à
résoudre de manière optimale le cas le pire
(qui est peu probable) et conduit à des algorithmes simples et très efficaces en moyenne.
On sait ainsi traiter des échantillons de
100 000 points en une dizaine de secondes
(Pentium III à 500 MHz).
Si calculer vite est important, calculer de
manière fiable l’est encore plus. Cette question est délicate, car les ordinateurs ne savent
généralement représenter les nombres qu’avec
une précision finie (un nombre fini de décimales). Ainsi, il est impossible de donner une
représentation à la fois numérique et exacte
de nombres comme π ou √2, qui comportent
une infinité de décimales. L’accumulation des
erreurs d’arrondis peut alors conduire à un
comportement anormal des programmes. Si
ces comportements sont bien connus, ils sont
difficiles à maîtriser, et la réalisation et la maintenance d’algorithmes fiables sont très coûteuses. Une part importante de la recherche
récente en géométrie algorithmique porte sur
ces questions et mêlent algorithmique, calcul
formel (où l’ordinateur manipule des symboles,
et non des nombres explicites) et arithmétique
des ordinateurs. Elles ont d’ores et déjà débouché sur le développement de bibliothèques de
logiciels permettant une programmation facile,
efficace et sûre, telle que la bibliothèque CGAL
(Computational Geometry Algorithms Library)
développée par une collaboration internationale d’universités et d’organismes de recherche.
Jean-Daniel Boissonnat
INRIA (Institut national de recherche en
informatique et en automatique), Sophia-Antipolis
Reconstruire des surfaces pour l’imagerie
91
Quelques références :
• J.-D. Boissonnat et M. Yvinec, Algorithmic geometry (Cambridge University Press, 1998).
• J.-D. Boissonnat et F. Cazals, « Smooth surface
reconstruction via natural neighbour interpolation of distance functions », dans Proceedings of
the 16 th Annual ACM Symposium of
Computational Geometry (2000).
• CGAL, The Computational Geometry
Algorithms Library, http://www.cgal.org.
précises, validées expérimentalement. Dans
bien des cas, et le calcul de la triangulation
de Delaunay en est un, l’introduction d’une
part de hasard autorise à ne pas chercher à
résoudre de manière optimale le cas le pire
(qui est peu probable) et conduit à des algorithmes simples et très efficaces en moyenne.
On sait ainsi traiter des échantillons de
100 000 points en une dizaine de secondes
(Pentium III à 500 MHz).
Si calculer vite est important, calculer de
manière fiable l’est encore plus. Cette question est délicate, car les ordinateurs ne savent
généralement représenter les nombres qu’avec
une précision finie (un nombre fini de décimales). Ainsi, il est impossible de donner une
représentation à la fois numérique et exacte
de nombres comme π ou √2, qui comportent
une infinité de décimales. L’accumulation des
erreurs d’arrondis peut alors conduire à un
comportement anormal des programmes. Si
ces comportements sont bien connus, ils sont
difficiles à maîtriser, et la réalisation et la maintenance d’algorithmes fiables sont très coûteuses. Une part importante de la recherche
récente en géométrie algorithmique porte sur
ces questions et mêlent algorithmique, calcul
formel (où l’ordinateur manipule des symboles,
et non des nombres explicites) et arithmétique
des ordinateurs. Elles ont d’ores et déjà débouché sur le développement de bibliothèques de
logiciels permettant une programmation facile,
efficace et sûre, telle que la bibliothèque CGAL
(Computational Geometry Algorithms Library)
développée par une collaboration internationale d’universités et d’organismes de recherche.
Jean-Daniel Boissonnat
INRIA (Institut national de recherche en
informatique et en automatique), Sophia-Antipolis
Reconstruire des surfaces pour l’imagerie
91
Quelques références :
• J.-D. Boissonnat et M. Yvinec, Algorithmic geometry (Cambridge University Press, 1998).
• J.-D. Boissonnat et F. Cazals, « Smooth surface
reconstruction via natural neighbour interpolation of distance functions », dans Proceedings of
the 16 th Annual ACM Symposium of
Computational Geometry (2000).
• CGAL, The Computational Geometry
Algorithms Library, http://www.cgal.org.