Spatial Information Theory. Foundations of Geographic Information Science

We survey the manifold variety of kinds of phenomena which come within the purview of geography and GI Science, and identify three key desiderata for a fully spatio-temporal geo-ontology which can do justice to those phenomena. Such a geo-ontology must (a) provide suitable forms of representation and manipulation to do justice to the rich network of interconnections between field-based and object-based views of the world; (b) extend the field-based and object-based views, and the forms of representation developed to handle them, into the temporal domain; and (c) provide a means to develop different views of spatio-temporal extents and the phenomena that inhabit them, especially with reference to those phenomena such as storms, floods, and wildfires which seem to present dual aspects as both object-like and process-like.

Scale is of great importance to the analysis of real world phenomena, be they enduring objects or perduring processes. This paper presents a new perspective on the concept of scale by considering it within two complementary ontological views. The first, called SNAP, recognizes enduring entities or objects, the other, called SPAN, perduring entities or processes. Within the meta-theory provided by the complementary SNAP and SPAN ontologies, we apply different theories of formal ontology such as mereology and granular partitions, and ideas derived from hierarchy theory. These theories are applied to objects and processes and form the framework within which we present tentative definitions of scale, which are found to differ between the two ontologies.

This paper describes categories for landscape elements in the language of the Yindjibarndi people, a community of Indigenous Australians. Yindjibarndi terms for topographic features were obtained from dictionaries, and augmented and refined through discussions with local language experts in the Yindjibarndi community. In this paper, the Yindjibarndi terms for convex landforms and for water bodies are compared to English-language terms used to describe the Australian landscape, both in general terms and in the AUSLIG Gazetteer. The investigation found fundamental differences between the two conceptual systems at the basic level, supporting the notion that people from different places and cultures may use different categories for geographic features.

Standard theories in mereotopology focus on relations of parthood and connection among spatial or spatio-temporal regions. Objects or processes which might be located in such regions are not normally directly treated in such theories. At best, they are simulated via appeal to distributions of attributes across the regions occupied or by functions from times to regions. The present paper offers a richer framework, in which it is possible to represent directly the relations between entities of various types at different levels, including both objects and the regions they occupy. What results is a layered mereotopology, a theory which can handle multiple layers (analogous to the layers of a lasagna) of spatially or spatiotemporally coincident but mereologically non-overlapping entities.

Spatial agents often have to infer global knowledge from local knowledge about orientations and distances. Thereby, the local knowledge based on sensor data is typically imprecise. We propose an approach that propagates orientation and distance intervals to produce global knowledge and compare it with qualitative reasoning calculi in the context of indoor mobile robot exploration. We combine this propagation method with a path-based and predominantly topological mapping approach and demonstrate how it can be utilized to solve the cycle detection problem.

To travel successfully in a dynamic space-time setting, wayfinders must project the impact of a changing environment onto future travel choices. When making decisions, however, people often fail to consider the impact of future changes. They instead overly rely on current system states. In addition, spatial information systems designed for wayfinders typically focus on current or historic travel information. To address these limitations, this paper presents an approach to structure the dynamic space-time environment of a wayfinder. With this structure, improved spatial information systems can be designed to support wayfinders in dynamic environments. To create this structure, four primitives of space-time wayfinding are presented: maximum travel speed, a starting point, barriers, and compulsions. Combining the speed limitation with each of the remaining three primitives creates distinctive partitions of space-time. To integrate all four primitives, a method of sequentially partitioning space-time is described which results in four partition categories that account for the different constraints of wayfinding. These partitions are described in a cognitively plausible manner using modal verbs can, may, must, and should. The creation of this structure along with these descriptive semantics creates a rich representation of the wayfinder’s space-time environment and allows for reasoning about space-time decision points and their impact on future possibilities.

This article suggests a second thought on two papers published in Cognitive psychology in 1978 and 1981. Both articles deal with systematic distortions in cognitive mapping and both are based on experiments conducted along the North American West Coast. The first, by Stevens and Coupe, deals with distortions due to hierarchical organization while the second, by Tversky, with distortions due to rotation. Our second thought follows a set empirical results from a study conducted along the (West) coast of Israel. These results suggest that the experiments, on the basis of which the above two forms of systematic distortions were determined, could have resulted from another form of systematic distortion that we term the edge effect.

We present a qualitative shape description which has previously been proven to be useful for object categorisation. The description is based on a set of shape primitives which we will restrict to a new subset of relations representing stylised curvature information. In contrast to other qualitative shape theories, this description enables us to distinguish different convex shapes. This is especially interesting from a cognitive point of view since these shapes show salient visual differences. It turns out that the distinction between two sides of a line together with the distinction between acute and obtuse angles make up a powerful concept of orientation information for shapes in two dimensions.

The scope of this paper is a qualitative description of terrain features that can be characterized using the silhouette of a terrain. The silhouette is a profile of a landform seen from a particular observer’s perspective. We develop a terrain language as a formal framework to capture terrain features. The horizon of a terrain silhouette is represented as a string. The alphabet of the terrain language comprises straight-line segments. These line primitives are classified according to three criteria: (1) the alignment of their slope, (2) their relative lengths, characterized by orders of magnitude, and (3) their differences in elevation, described by an order relation. We employ term rewriting rules to identify terrain features at different granularity levels. There are three kinds of rules: aggregation, generalization, and simplification rules. The aggregation rules generate a description of the terrain features at a given granularity level. For a terrain description the generalization and simplification rules specify the transi- tion from a finer granularity level to a coarser one. An example shows how the three kinds of rules lead to a terrain description at different granularity levels.

This paper describes an architecture for dynamically handling spatial relations in an incremental, nonmonotonic diagrammatic reasoning system. The architecture represents jointly exhaustive and pairwise disjoint (JEPD) spatial relation sets as nodes in a dependency network. These spatial relation sets include interval relations, relative orientation relations, and connectivity relations, but in theory could include any JEPD spatial relation sets. This network then caches dependencies between low-level spatial relations, allowing those relations to be easily assumed or retracted as visual elements are added or removed from a diagram. For example, in the architecture’s Undo mechanism, the dependency network can quickly reactivate cached spatial relations when a previously-deleted element is restored. As part of this work, we describe how the system supports higher-level reasoning, including support for creating default assumptions. We also describe how this system was integrated with an existing drawing program and discuss its possible use in diagrammatic and geographic reasoning.

Geosimulation aims at modeling systems at the scale of individuals and entity- level units of the built environment and provides a new way to simulate how geographic spaces can be used by their future users, particularly in urban environments. In the MAGS Project we are developing a generic software platform for the creation of Multi-Agent Geo-Simulations involving several thousand agents interacting in virtual geographic environments (in 2D and 3D) and endowed with spatial cognitive capabilities (perception, navigation, reasoning). Our approach is currently applied to the simulation of crowd behaviors in urban environments.

Numerous cognitive studies have indicated that the form and complexity of route instructions may be as important to human navigators as the overall length of route. Most automated navigation systems rely on computing the solution to the shortest path problem, and not the problem of finding the “simplest” path. This paper addresses the issue of finding the “simplest” paths through a network, in terms of the instruction complexity. We propose a “simplest” paths algorithm that has quadratic computation time for a planar graph. An empirical study of the algorithm’s performance, based on an established cognitive model of navigation instruction complexity, revealed that the length of a simplest path was on average only 16% longer than the length of the corresponding shortest path. In return for marginally longer routes, the simplest path algorithm seems to offer considerable advantages over shortest paths in terms of their ease of description and execution. The conclusions indicate several areas for future research: in particular cognitive studies are needed to verify these initial computational results. Potentially, the simplest paths algorithm could be used to replace shortest paths algorithms in any automated system for generating human navigation instructions, including in-car navigation systems, Internet driving direction servers, and other location-based services.

The discovery of services that are appropriate for answering a given question is a crucial task in the open and distributed environment of web services for geographic information. In order to find these services the concepts underlying their implementation have to be matched against the requirements resulting from the question. It is in this matchmaking process where semantic heterogeneity has to be tackled. Whether semantic interoperability can be achieved depends on the quality of the information available to the matchmaker on the semantics of requirements and resources. The explicitness, structuring and formality of this information can differ considerably leading to different types of matchmaking. In this paper a framework is presented for classifying the approaches that are currently employed or proposed for achieving semantic interoperability according to these criteria. The application of the framework is illustrated by analyzing possible solutions to three examples of semantic interoperability problems.

This paper introduces a relative adjacency operator that characterises mutual relationships between regions in a pseudo-partition. The relative adjacency is computerised from the dual graph of a spatial pseudo-partition. It is flexible enough to reflect different degrees and clusters of relative adjacencies by minimising or maximising the effect of neighbouring and remote regions. The properties of the relative adjacency are illustrated by some canonical examples and a case study.

The article presents a qualitative region-based approach to the representation of extension. A geometry of incidence and ordering is taken as a basis to characterize the concept of extension founded on the congruence of certain regions (called places) which have equal extension into all directions. The notion of extension of regions is derived from the sizes of places—not from the distance between points as in classical geometry—and represented by size intervals. A geometric specification of granular or scale-specific spatial contexts and of the local extension of a region is then derived. Extension relative to a spatial context is used to formally specify conditions under which object regions can be classified e.g. as punctual, linear, or planar in the context.

Reasoning about spatial relevance is important for intelligent spatial information retrieval. In heterogeneous and distributed systems like the Semantic Web, spatial reasoning has to be based on light-weight, interoperable and easy-to-use spatial metadata.

In this paper we present an approach to an intuitive and user-friendly creation and application of spatial metadata that are used for spatial relevance reasoning. The metadata are based on discrete approximations of place name regions. Based on knowledge about cognitive aspects of preferred spatial models, our approach allows for the representation and intuitive modelling of indeterminate regions in addition to regions with well-known boundaries.

This paper looks at Coppel’s axioms for convexity, and shows how they can be applied to discrete spaces. Two structures for a discrete geometry are considered: oriented matroids, and cell complexes. Oriented matroids are shown to have a structure which naturally satisfies the axioms for being a convex geometry. Cell complexes are shown to give rise to various different notions of convexity, one of which satisfies the convexity axioms, but the others also provide valid notions of convexity in particular contexts. Finally, algorithms are investigated to validate the sets of a matroid, and to compute the convex hull of a subset of an oriented matroid.

The relationship between less detailed and more detailed versions of data is one of the major issues in processing geographic information. Fundamental to much work in model-oriented generalization, also called semantic generalization, is the notion of an equivalence relation. Given an equivalence relation on a set, the techniques of rough set theory can be applied to give generalized descriptions of subsets of the original set. The notion of equivalence relation, or partition, has recently been significantly extended by the introduction of the notion of a granular partition. A granular partition provides what may be thought of as a hierarchical family of partial equivalence relations. In this paper we show how the mechanisms for making rough descriptions with respect to an equivalence relation can be extended to give rough descriptions with respect to a granular partition. In order to do this, we also show how some of the theory of granular partitions can be reformulated; this clarifies the connections between equivalence relations and granular partitions. With the help of this correspondence we then can show how the notion of hierarchical systems of partial equivalence classes relates to partitions of partial sets, i.e., partitions of sets in which not all members are known. This gives us new insight into the relationships between roughness and vagueness.

Natural language requests involving vague spatial concepts are not easily communicated to a GIS because the meaning of spatial concepts depends largely on the contexts (such as task, spatial contexts, and user’s personal background) that may or may not be available or specified in the system. To address such problems, we developed a collaborative dialogue approach that enables the system and the user to construct shared knowledge about relevant contexts. The system is able to anticipate what contextual knowledge must be shared, and to form a plan to exchange contextual information based on the system’s belief on who knows what. To account those user contexts that are not easily communicated by language, direct feedback approach is used to refine the system’s belief so that the intended meaning is properly grounded. The approach is implemented as a dialogue agent, GeoDialogue, and is illustrated through an example dialogue involving the communication of the vague spatial concept near.

How can we represent spatial information in maps in a cognitively adequate way? The present article outlines a cognitive conceptual approach that proposes primitive conceptual elements from which maps can be constructed. Based on work in geography that starts with abstract models of geographic phenomena, namely modelisation chorematique by R. Brunet (1980, 1987), we coin primitive conceptual elements of route directions wayfinding choremes. Sketch map drawings were analyzed as they obey the same medial constraints as maps but are constructed in a way that provides insights into human conceptions. A distinction between structural and functional aspects of wayfinding presents a useful method to gain further knowledge about human conceptualizations and leads to a practicable cognitive conceptual approach to map construction.

This paper describes a technique for creating generalizable depictions of cognitive spaces from natural language documents, and presents a Web-based system that uses this procedure to visualize structure in geographic discourse. We implement a concept abstraction routine that leverages a lexical ontology to infer the semantics of discussion terms at increasing levels of generalization. A Web discussion medium that uses the Delphi method to guide geographic discourse serves as the framework from which concept structures are elicited. Delphi discussants explore these structures using two Web-enabled visualization schemes: Self-Organizing Maps and concept graphs. These visualization tools rely on a set of concept similarity measures tailored to conceptual information at multiple levels of abstraction. The cognitive spaces produced using this system can reveal key themes in a domain, and can help guide the creation of domain ontologies. We apply these tools to explore concept structures in the field of human-environment interaction.

When describing routes in urban environments, speakers usually refer to both street names and visual landmarks. However, a navigational system can be designed which only refers to streets or, alternatively, only to landmarks. Does it make any difference which type of information users are provided with? The answer to this question is crucial for the design of navigational aids. We report two experiments. The first one showed that in a wayfinding task, route directions referring to streets were less effective than those referring to landmarks for guidance purposes. The second experiment showed that when people generate route directions, they tend to produce less street than landmark information. These studies provide a further illustration of the critical role of landmarks in route directions.

The navigation task is a very demanding application for mobile users. The algorithms of present software solutions are based on the established methods of car navigation systems and thus exhibit some inherent disadvantages: findings in spatial cognition research have shown that human users need landmarks for an easy and successful wayfinding. Typically, however, an object is not a landmark per se, but can be one relative to its environment. Unfortunately, these objects are not part of route guidance information systems at the moment.

Therefore, it is an aim of research to make landmarks for routing instructions available. In this paper we focus on a method to automatically derive landmarks from existing spatial databases. Here a new approach is presented to investigate existing spatial databases and try to extract landmarks automatically by use of a knowledge discovery process and data mining methods. In this paper two different algorithms, the classification method ID3 and the clustering procedure Cobweb, are investigated, whether they are suitable for discovering landmarks.

Two aspects of visual attention, the selection of environmental features and the engagement of attention on those features, were examined in an experimental study using a slide-presentation simulation of route experience. Results showed that (a) after learning, viewers’ knowledge of spatial relations among high-information regions was more accurate than their knowledge of spatial relations among low-information regions; (b) during learning, viewers were more selective when looking at high-information regions than when looking at low-information regions; (c) during learning, viewers were slower to disengage attention when looking at high-information regions than when looking at low-information regions; and (d) during learning, the most common type of visual activity when viewers saw high-information regions were saccades between landmarks and the path’s vanishing point in the scene. These findings indicate that although route learning is a relatively simple and wellpracticed task, it involves attention in terms of the selection of highly informative regions for in-depth coding of spatial relations.