Spatial News

Identifying factors of geographic event conceptualisation

Klippel, A., Worboys, M. and Duckham, M., 2008, Identifying factors of geographic event conceptualisation. International Journal of Geographical Information Science, 22, pp. 183-204.

The present paper examines whether the formal topological characterisation of spatial relations between moving geographic regions provides an adequate basis for the human conceptualisation of motion events for those regions. The paper focuses on gradual changes in topological relationships caused by continuous transformations of the regions (specifically, translations). Using a series of experiments, the conceptualisation and perception of conceptual neighborhoods is investigated. In particular, the role of conceptual neighborhoods in characterising motion events is scrutinised. The experiments employ a grouping paradigm and a custom-made tool for presenting animated icons. The analysis examines whether paths through a conceptual neighborhood graph sufficiently characterise the conceptualisation of the movement of two regions. The results of the experiments show that changes in topological relations - as detailed by paths through a conceptual neighborhood graph - are not sufficient to characterise the cognitive conceptualisation of moving regions. The similarity ratings show clear effects of perceptually and conceptually induced groupings such as identity (which region is moving), reference (whether a larger or a smaller region is moving), and dynamics (whether both regions are moving at the same time).

Conceptual Neighborhoods of Topological Relations between Lines

R. Reis, M. Egenhofer, and J. Matos, Conceptual Neighborhoods of Topological Relations between Lines, in: A. Ruas and C.Gold (eds.), The 13th International Symposium on Spatial Data Handling (SDH 2008), Montpellier, France
Springer, June 2008.

Conceptual neighborhood graphs capture the similarity among qualitative relations. This paper derives the graphs for the thirty-three topological relations between two crisp, undirected lines and for the seventy-seven topological relations between two lines with uncertain boundaries. The analysis of the graphs shows that the normalized node degree increases, from the crisp to the broad-boundary lines, roughly at the same degree as it increases for crisp lines that are transformed from R1 into R2.

Perceptual Sketch Interpretation

Markus Wuersch and Max J. Egenhofer, Perceptual Sketch Interpretation, in: A. Ruas and C.Gold (eds.), The 13th International Symposium on Spatial Data Handling (SDH 2008), Montpellier, France Springer, June 2008.

An automated extraction of regions from sketches can be of great value for multi-modal user interfaces and for interpreting spatial data. This paper develops the Perceptual Sketch Interpretationalgorithm, which employs the theory of topological relations from spatial reasoning as well as continuity and good gestalt from gestalt theory in order to model people's perception. The Perceptual Sketch Interpretation algorithm extracts regions iteratively, removing one region at each a time, thus making the remaining sketch simpler and easier to interpret. The evaluation of the algorithm shows that the use of gestalt theory empowers the algorithm to correctly identify regions and saves processing time over other approaches.

Spatial Reasoning with a Hole

Max J. Egenhofer and Maria Vasardani, Spatial Reasoning with a Hole, in: S. Winter, M. Duckham, L. Kulik, and B. Kuipers (eds.), Conference on Spatial Information Theory (COSIT '07), Melbourne, Australia, Lecture Notes in Computer Science, Vol. 4736, Springer, pp. 303-320, September 2007.

Cavities in spatial phenomena require geometric representations of regions with holes. Existing models for reasoning over topological relations either exclude such specialized regions (9-intersection) or treat them indistinguishably from regions without holes (RCC-8). This paper highlights that inferences over a region with a hole need to be made separately from, and in addition to, the inferences over regions without holes. First the set of 23 topological relations between a region and a region with a hole is derived systematically. Then these relations' compositions over the region with the hole are calculated so that the inferences can be compared with the compositions of the topological relations over regions without holes. For 266 out of the 529 compositions the results over the region with the hole were more detailed than the corresponding results over regions without holes, with 95 of these refined cases providing even a unique result. In 27 cases, this refinement up to uniqueness compares with a completely undetermined inference for the relations over regions without holes.

Metric Details of Topological Line-Line Relations

Kostas Nedas, Max J. Egenhofer, and Dominik Wilmsen, Metric Details of Topological Line-Line Relations International Journal of Geographical Information Science 21 (1): 21-48, 2007.

Many real and artificial entities in geographic space, such as transportation networks and trajectories of movement, are typically modeled as lines in geographic information systems. In a similar fashion, people also perceive such objects as lines and communicate about them accordingly as evidence from research on sketching habits suggests. To facilitate new modalities like sketching that rely on the similarity among qualitative representations, oftentimes multi-resolution models are needed to allow comparisons between sketches and database scenes through successively increasing levels of detail. Within such a setting, topology alone is sufficient only for a coarse estimate of the spatial similarity between two scenes, whereas metric refinements may help extract finer details about the relative positioning and geometry between the objects. The 9-intersection is a topological model that distinguishes 33 relations between two lines based on the content invariant (empty-nonempty intersections) among boundaries, interiors, and exteriors of the lines. This paper extends the 9-intersection model by capturing metric details for line-line relations through splitting ratiosand closeness measures. Splitting ratios, which apply to the 9-intersection's non-empty values, are normalized values of lengths and areas of intersections. Closeness measures, which apply to the 9-intersection's empty values, are normalized distances between disjoint object parts. Both groups of measures are integrated into compact representations of topological relations, thereby addressing topological and metric properties of arbitrarily complex line-line relations.

Geo-Mobile Query-by-Sketch

David Caduff and Max J. Egenhofer, Geo-Mobile Query-by-Sketch, International Journal of Web Engineering and Technology, 3 (2): 157-175, 2007.

The advent of wireless technology, such as cellphones, PDAs, tablet PCs, and sub-notebooks, allows tranferring portions of traditional desktop-based GIS technology to mobile environments. This paper introduces Geo-Mobile Query-by-Sketch, a sketch-based spatial querying system for mobile GIS environment that combines techniques for spatial querying with mobile technologies. The system implements and adaptive client-server architecture, which copes with restrictions of mobile environments, such as fluctuating bandwidth and fre quent disconnections. The core concept analyzed is the mobile sketch, a multi-representation data structure of a sketched scene, which enables an adaption strategy that is tialored to the available transmission rates. We analyze the transmission cost of Geo-Mobile Query-by-Sketch and develop a protocol that optimizes the adaption level in order to guarantee quality of service.

The Head-Body-Tail Intersection for Spatial Relations Between Directed Line Segments

Yohei Kurata and Max J. Egenhofer, The Head-Body-Tail Intersection for Spatial Relations Between Directed Line Segments, in: M. Raubal, H. Miller, A. Frank, and M. Goodchild (eds.) GIScience 2006—4th International Conference on Geographic Information Science, Lecture Notes in Computer Science, Vol. 4197, pp. 269-286.

Abstract

Directed line segments are fundamental geometric elements used to model through their spatial relations such concepts as divergence, confluence, and interference. A new model is developed that captures spatial relations between pairs of directed line segments through the intersections of the segments' heads, bodies, and tails. This head-body-tail intersection identifies 68 classes of topological relations between two directed line segments highlighting two equal-sized subsets of corresponding relations that differ only by their empty and non-empty body-body intersections. The relations' conceptual neighborhood graph takes the shape of a torus inside a torus, one for each subset. Another 12 classes of topological relations are distinguished if the segments' exteriors are considered as well, lining up such that their conceptual neighborhood graph forms another torus that contains the other two tori. These conceptual neighborhoods as well as the relations' composition table enable spatial inferences and similarity assessments in a consistent and reasoned manner.

Changes in Topological Relations when Splitting and Merging Regions

M. Egenhofer and D. Wilmsen, Changes in Topological Relations with Splitting and Merging Regions, in: A. Riedl, W. Kainz, and G. Elmes (eds.), Progress in Spatial Data Handling -- 12th International Symposium on Spatial Data Handling, Springer, pp. 339-352.

Abstract

This paper addresses changes in topological relations as they occur when splitting a region into two. It derives systematically what qualitative inferences can be made about binary topological relations when one region is cut into two pieces. The new insights about the possible topological relations obtained after splitting regions form a foundation for high-level spatio-temporal reasoning without explicit geometric information about each object’s shapes, as well as for transactions in spatio-temporal databases that want to enforce consistency constraints.

GeoSpatial Semantics--First International Conference, GeoS 2005

A. Rodríguez, I. Cruz, M. Egenhofer, and S. Levashkin (editors), GeoSpatial Semantics--First International Conference, GeoS 2005, Lecture Notes in Computer Science, Vol. 3799, Spinger, New York, 2005.

This book contains the fully refereed papers of the First International Symposium on Geospatial Semantics, GeoS 2005, to be held in Mexico City, Mexico in November 2005.

Ontology-Driven Map Generalization

L. Kulik, M. Duckham, and M. Egenhofer, Ontology-Driven Map Generalization Journal of Visual Languages and Computing 16 (3): 245-267, 2005.

Abstract

Different users of geospatial information have different requirements of that information. Matching information to users' requirements demands an understanding of the ontological aspects of geospatial data. In this paper, we present an ontology-driven map generalization algorithm, called DMin, that can be tailored to particular users and users' tasks. The level of detail in a generated map is automatically adapted by DMin according to the semantics of the features represented. The DMin algorithm is based on a weighting function that has two components: (1) a geometric component that differs from previous approaches to map generalization in that no fixed threshold values are needed to parameterize the generalization process and (2) a semantic component that considers the relevance of map features to the user. The flexibility of DMin is demonstrated using the example of a transportation network.

Spherical Topological Relations

M. Egenhofer, Spherical Topological Relations, Journal on Data Semantics III: 25-49, 2005.

Abstract

Analysis of global geographic phenomena requires non-planar models. In the past, models for topological relations have focused either on a two-dimensional or a three-dimensional space. When applied to the surface of a sphere, however, neither of the two models suffices. For the two-dimensional planar case, the eight binary topological relations between spatial regions are well known from the 9-intersection model. This paper systematically develops the binary topological relations that can be realized on the surface of a sphere. Between two regions on the sphere there are three binary relations that cannot be realized in the plane. These relations complete the conceptual neighborhood graph of the eight planar topological relations in a regular fashion, providing evidence for a regularity of the underlying mathematical model. The analysis of the algebraic compositions of spherical topological relations indicates that spherical topological reasoning often provides fewer ambiguities than planar topological reasoning. Finally, a comparison with the relations that can be realized for one-dimensional, ordered cycles draws parallels to the spherical topological relations.

Advances in Spatial and Temporal Databases--9th International Symposium, SSTD 2005

C. Bauzer Medeiros, M. Egenhofer, and E. Bertino (editors), Advances in Spatial and Temporal Databases--Nineth International Symposium, SSTD 2005, Lecture Notes in Computer Science, Vol. 3633, Spinger, New York, 2005.

This book contains the fully refereed papers of the 9th International Symposium on Spatial and Temporal Databases, SSTD 2005, held in Angra dos Reis, Brazil in August 2005.