Représentations hiérarchiques de collections de petits rectangles

Un aperçu didactique est présenté sur les structures de données hiérarchiques pour représenter des collections de petits rectangles. Les rectangles sont souvent utilisés comme une approximation de formes pour lesquelles ils servent d'objet minimal rectiligne englobant. Ils apparaissent dans des applications en cartographie ainsi que dans la vérification des règles de conception pour l'intégration très à grande échelle (VLSI). Les différentes structures de données sont discutées en termes de la manière dont elles soutiennent l'exécution de requêtes impliquant des relations de proximité. L'accent est mis sur les requêtes d'intersection et de sous-ensemble. Plusieurs types de représentations sont décrites. Certaines sont conçues pour être utilisées avec le paradigme de balayage de plan, qui fonctionne bien pour des collections statiques de rectangles. D'autres sont orientées vers des collections dynamiques. Dans ce dernier cas, une représentation réduit chaque rectangle à un point dans un espace multidimensionnel supérieur et traite le problème comme impliquant des données ponctuelles. L'autre représentation est basée sur la surface, c'est-à-dire qu'elle dépend de l'extension physique de chaque rectangle.