Spatial data collections with an incomplete coverage yield regions with holes and separations that often cannot be filled by interpolation. Geosensor networks typically generate such configurations, and with the proliferation of sensor colonies, there is now an urgent need to provide users with better information technologies of cognitively plausible methods to search for or compare available spatial data sets that may be incomplete. The objective of the investigations is to advance knowledge about qualitative spatial relations for spatial regions with holes and/or separations.

The core activity is the study of the interplay between topological spatial relations with holed regions and topological spatial relations with separated regions to address the potentially complex configurations that feature both holes and separations. Three characteristics of such a set of topological relations are addressed: the formalization of a sound set of relations at a granularity that allows for the distinction of the salient features of holed and separated regions, while offering the opportunity to generalize to coarser relations in a meaningful and consistent way; the relaxation of such relations so that the determination of the most similar relations follows immediately from the applied methodology; and the qualitative inference of new information from the composition of such relations to identify inconsistencies and to drawn information that is not immediately available from individual relations.

The hypothesis is that combining the relation formalization with sound similarity and composition reasoning yields critical insights for a sufficiently expressive, common approach to modeling topological relations for holed regions and regions with separations. The resulting theory of topological spatial relations highlights a parallelism between relations with holed regions and regions with separations, which is most apparent when these regions are embedded on the surface of the sphere, while some parts of these regularities are often hidden in the usual planar embedding.

Since topological relations are qualitative spatial descriptions, they come close to people's own reasoning, so that a better understanding of the relations for compound spatial objects will have ramifications for qualitative spatial reasoning, without a need for drawing graphical depictions to make inferences. It also lays the foundation for linguistic constructs to communicate in natural language spatial configurations, ultimately leading to talking maps. An immediate impact of this theory of topological relations between holed and separated regions is on the querying and reasoning about dataset that are gathered by geosensor networks.

For further information see the project web page: URL:

Project Report

This project developed formal models for the semantics and inferences of topological relations for complexly structured spatial objects. Such objects are often the result of analyses obtained from geosensor network data and include regions that have holes and separations. The major intellectual findings relate to capturing the topology of entire spatial scenes, not only binary relations between spatial objects. We found that a complete capture of the topology of an entire spatial scene needs two components: (1) the topological hull to capture surrounded components (not only those surrounded by a single spatial object, but also those surrounded by a collection of connected objects) and (2) an account for the occurrence of intersections between the boundaries of regions. Topological hull and sequence of boundary-intersections are orthogonal (i.e., the information captured by one cannot be replaced by the information captured by the other). When used together, information about the topological hulls and boundary sequences capture the topology of entire spatial scenes. The model we developed allows for the comparison of spatial scenes and enables the construction of a topologically unambiguous depiction of spatial scenes. A unique feature of configurations with holes is the spatial relations surrounds (and conversely surrounded by), which is not part of the standard set of binary topological relations. We formalized an algebraic construction for the relation surrounds within a partition and provided a complementary graph-theoretic approach for the detection of the surrounds conditions created by the operations within the algebra. Four refinements of a surrounds relations were identified: (1) a holed configuration that surrounds nothing, (2) a holed configuration that surrounds an object without direct contact, (3) a holed configuration that surrounds an object with partial contact, and (4) a holed configuration that surrounds an object with full contact. Outcomes of broader impacts include the training of two doctoral students, who co-authored four articles published about the project’s results, and the mentoring of the summer projects of fifteen Upward Bound High School students (interested in pursuing STEM college majors) by one of the doctoral students. During the project period that Principal Investigator co-chairs the program committee of the 10th International Conference on Spatial Information Theory (COSIT 2011), held in Belfast, ME.

National Science Foundation (NSF)
Division of Information and Intelligent Systems (IIS)
Standard Grant (Standard)
Application #
Program Officer
Maria Zemankova
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
University of Maine
United States
Zip Code