Abstract FR:

Les structures de donnees usuelles procedent de deux facons : soit en organisant recursivement les donnees manipulees, soit en subdivisant recursivement l'espace les contenant. Des exemples des premieres sont les arbres binaires de recherche en dimension un ou les arbres k - d en dimension d, et des illustrations des secondes sont les tables de hachage en dimension un ou les grilles uniformes et recursives en plus grande dimension. Pourtant tres utilisees en infographie, les structures de ce second type n'ont pas recu l'attention de leurs homologues de telle sorte que leurs proprietes asymptotiques, les compromis espace memoire requis - performances auxquels elles donnent lieu, ou encore le type de donnees pour lesquelles elles sont le mieux adaptees sont mal connus. Ce travail est consacre a ces questions et les contributions sont de trois ordres. Dans le cadre particulier du lancer de rayon, nous proposons d'abord une nouvelle structure de donnees appelee hug ou hierarchy of uniform grids, hierarchique non recursive et basee sur la repartition spatiale des donnees manipulees. Nous montrons qu'elle permet d'une part de mieux comprendre les proprietes induites par les subdivisions recursives, et que d'autre part elle conduit a des performances notablement meilleures pour certains types de scenes. Ensuite et afin d'etudier la complexite de l'un des algorithmes utilises pour sa construction, nous considerons certains aspects de la combinatoire d'arrangements de segments sur une droite et de cones sur un cercle. Enfin, nous presentons quelques resultats de geometrie integrale qui constituent un premier pas vers une analyse en moyenne de nos structures de donnees et qui fournissent des methodes de classification automatique de scenes.