A containment-first search algorithm for higher-order analysis of urban topology

Abstract

Research has revealed the importance of the concepts from the mathematical areas of both topology and graph theory for interpreting the spatial arrangement of spatial entities. Graph theory in particular has been used in different applications of a wide range of fields for that purpose, however not many graph-theoretic approaches to analyse entities within the urban environment are available in the literature. Some examples should be mentioned though such as, Bafna (2003), Barr and Barnsley (2004), Bunn et al. (2000), Krüger (1999), Nardinochi et al. (2003), and Steel et al. (2003). Very little work has been devoted in particular to the interpretation of initially unstructured geospatial datasets. In most of the applications developed up-to-date for the interpretation and analysis of spatial phenomena within the urban context, the starting point is to some extent a meaningful dataset in terms of the urban scene. Starting at a level further back, before meaningful data are obtained, the interpretation and analysis of spatial phenomena are more challenging tasks and require further investigation. The aim of retrieving structured information from initial unstructured spatial data, translated into more meaningful homogeneous regions, can be achieved by identifying meaningful structures within the initial random collection of objects and by understanding their spatial arrangement (Anders et al., 1999). It is believed that the task of understanding topological relationships between objects can be accomplished by both applying graph theory and carrying out graph analysis (de Almeida et al., 2007).