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
