AN OVERVIEW OF THE USE OF QUADTREES AND RELATED 
Mas HIERARCHICAL DATA STRUCTURES IN GEOGRAPHIC 
INFORMATION SYSTEMS 
Hanan Samet 
pour la 
S cette ; 
», les Department of Computer Science 
s dans University of Maryland 
ype de College Park, MD 20742 
pixel SA 
de la U.S.A. 
ication 
ssives. 
iges de 
jit les 
a donc ABSTRACT 
Dn, Sans 
Representation is an important issue in geographic information 
systems. A wide number of representations is currently in issue. 
Recently, there has been much interest in hierarchical data structure 
such as quadtrees and octrees. They are compact and, depending on 
the nature of the region, they save space as well as time and also 
facilitate operations such as search. In this paper we give a brief 
overview of the quadtree data structure and related research results. 
Examples will be drawn from a functioning geographic information 
system that uses the quadtree as the underlying representation. 
UTILISATION DE LA QUADRIPARTITION ET DES STRUCTURES 
HIERARCHIQUES CONNEXES DE DONNEES DANS LES SYSTEMES 
D'INFORMATION GÉOGRAPHIQUE : APERÇU 
RÉSUMÉ 
Dans les systèmes. d'information géographique, la 
représentation est un point d'intérêt important. On se 
penche actuellement sur un grand nombre de représentations. 
Ces derniers temps, on s'est beaucoup intéressé aux 
structures hiérarchiques des données, comme la 
quadripartition et l'arbre octogonal. Ces structures sont de 
faible encombrement et, selon la nature de la région, elles 
permettent d'économiser temps et espace et facilitent 
certaines opérations, comme la recherche. Dans cette 
présentation, nous...donnons un .bre£...aperçu* de la 
quadripartition et des résultats de recherches à ce sujet. 
Nous illustrons notre propos à l'aide d'exemples de systèmes 
d'information géographique fonctionnels dont le mode de 
représentation sous-jacent est la quadripartition. 
337