A. Greiner, L. Jacomme, F. Pétrot, F. Wajsbürt Investigations on Alliance Rectangle Data Structure for VLSI/CAD Algorithms Ce rapport décrit une nouvelle structure de données permet­ tant une recherche efficace pour le dessin des masques VLSI rec­ tilinéaires. Cette structure offre d'excellentes performances dès lors qu'il y a suffisement de mémoire interne disponible. Elle peut néanmoins être ajustée afin d'économiser de la mémoire, au détriment de la vitesse de la procédure de recherche. Ces hautes performances sont atteintes par le découpage du dessin en fenêtres carrées, permettant ainsi à tous les rectangles d'une aire donnée d'être accessible en une complexité temporelle de O(1). Le rapport vitesse sur mémoire est dépendant de la surface choisie pour les fenêtres. La structure offre des temps d'exécution presque linéaire en fonction du nombre de rectangles. Elle tient compte des exigences réelles d'implémentation: struc­ turation nécessaire au déroulement d'algorithmes hiérarchiques et prise en compte des niveaux technologiques pour la représentation efficace des masques.