RIA: Formalization, Inference, and Query Processing of Spatial Relations in Geographic Space

Interim Report, Year 1

• First, we planned to formally determine the properties of topological relations and derive the composition of two topological relations between point-, line-, and region-objects in R2. This task was completed. A Prolog program has been developed to derive the composition tables for the following combinations of topological relations (code will be made available on our FTP site): line-line with line-line, line-region with region-line, region-line with line-region, and region-line with line-region. We also developed a formalism to describe detailed topological relations, up to isomorphism, based on the successful model of the 4-intersection.
• We also made major progress with the formalization topological relations between regions with holes, a task we didn't plan for the first year. This advancement will enable us to demonstrate that our future findings can be generalized to more complex spatial objects than just disk-line objects.
• Beyond our initial goals, we were able to start the investigation of consistency among multiple topological relations, as it is particularly important for approximate spatial reasoning.
• As tasks 2 and 3 we had planned to investigate isolated distance and direction reasoning. We found that isolated reasoning about distances or directions has only little power, therefore, we concentrated on integrated distance- and direction-reasoning and found that this combination provides considerably more precise inferences.
• Finally, we implemented a first prototype of a spatial reasoner that is based on isolated spatial reasoning. This was developed in Think C and code has been made available on our FTP site.

All completed tasks have been documented in papers, theses, and technical papers, some of which have been published already in refereed conferences or have been accepted in refereed journals. A complete list of publications is enclosed, as well as reprints of published journal papers acknowledging support from IRI-9309230.

During year 2, we plan to focus on Integrated Spatial Reasoning with the following tasks:

• Using the results from the formalization of cardinal direction between point-like objects and the solutions to extending topological relations to higher co-dimensions, direction relations will be generalized to deal with extended objects.

• Develop efficient algorithms to implement reasoning mechanisms about individual qualitative spatial relations, particularly considering the dependency among qualitative and quantitative representations.

List of Publications

• Definitions of Line-Line Relations for Geographic Databases
  M. Egenhofer
  IEEE Data Engineering 16 (3): 40-46, 1994.

• A Model for Detailed Binary Topological Relationships
  M. Egenhofer
  Geomatica 47 (3 & 4): 261-273, 1993.

• Topological Relations between Regions with Holes
  M. Egenhofer, E. Clementini, and P. di Felice
  International Journal of Geographical Information Systems, 8 (2): 129-144, 1994.

• The Geographer's Desktop: A Direct-Manipulation User Interface for Map Overlay
  M. Egenhofer and J. Richards
  Autocarto 11, Minneapolis, MN, R. McMaster and M. Armstrong (editors), pp. 63-71, 1993.

• A Critical Comparison of the 4-Intersection and 9-Intersection Models for Spatial Relations: Formal Analysis
  M. Egenhofer, J. Sharma, and D. Mark
  Autocarto 11, Minneapolis, MN, R. McMaster and M. Armstrong (editors), pp. 1-11, 1993.

• Formalizing Importance: Parameters for Settlement Selection from a Geographic Database
  D. Flewelling and M. Egenhofer
  Autocarto 11, Minneapolis, MN, R. McMaster and M. Armstrong (editors), pp. 167-175, 1993.

• Qualitative Distance and Direction Reasoning in Geographic Space
  J.-H. Hong
  Ph.D. Thesis, Department of Surveying Engineering, University of Maine, Orono, 1994.

• Interaction with GIS Attribute Data Based on Categorical Coverages
  G. Volta and M. Egenhofer
  European Conference on Spatial Information Theory, Marciana Marina, Italy
  A. Frank and I. Campari (eds.), Lecture Notes in Computer Science, Vol. 716, Springer-Verlag, pp. 215-233, September 1993.