A Graph-based Technique for Higher Order Topological Data Structure Visualisation

Abstract

Interpretation and analysis of spatial phenomena is a highly time consuming and laborious task in several fietds of the Geomatics world (Anders et al., 1999). That is why the automation of those tasks is especially needed in areas such as Geographical Information Science (GlScience). Carrying out these tasks in the context of an urban scene is particulariy challenging given its complexity: relatively small component elements and itt"it g"nrially complei spatial pattern (Eyton, 1993, and Barr & Barnsley, 1996, both cited in Barnsley and Barr, 1997). Topology is a particularly important research area in the field of GlScience, for it is a central àefining feature of a geographical information system (GIS). But, as far as topological relàtionships between spatial objects are concerned, "generally speaking .ottt.Àporary desktop bIS packages do not support further information beyond the first level oi adjâcency" (Theobald, 2001). Therefore, this research project focused on scene analysis bi buiiding up a technique for the better understanding of topological relationships between vector-based GIS objects, beyond the fnst level of adjacency. Another initial interest was to investigate the possible use of graph theory for this purpose. To date, this mathematical framework has been used in different applications in a wide range of fields to represent connections and relationships between spatial entities. Several u,rtùo6 (including Laurini and Thompson, 1992) have maintained that "this particular tool is extremely valuable and efficient in storing and describing the spatial structure of geographicil entities and their spatial arrangement". Theobald (2001) added that "concepts àf gruptt theory allow us to extend the standard notion of adjacency". The aim of retrieving structured information translated into more meaningful homogeneous regions, for instancJ fro* an initial unstructured data set, may be achieved by identifuing mJaningful structures within the initial random collection of objects and by understanding the spatial arrangement between them. We believe that applying graph theory and carrying out graph analysis may accomplish this.