Abstract
Geographic objects and phenomena may gradually change their location, orientation, shape, and size over time. A qualitative change occurs if the deformation of an object affects its topological relationship with respect to another object. The observation of such changes is particularly interesting, because qualitative changes frequently require different decisions or trigger new actions. Investigations of a closed set of mutually exclusive binary topological relationships led to a formal model to determine for each topological relationship the relationships closest to it. Applied to the entire set of binary topological relationships between spatial regions, this model describes a partial order over topological relationships and provides a measure to assess how far two relationships are apart from each other. The changes to the binary topological relationship caused by such deformations as translation, rotation, reduction, and expansion of an object are mapped onto this graph. The graphs show characteristic traverses for each kind of deformation. Using these characteristic traverses as knowledge about deformations, one can infer from multiple observations the kind of deformation that caused the change and predict the next topological relationship. Particularly, it provides answers to three kinds of qualitative space-time inferences: (1) Given a process and a state, what is the next most likely state? (2) Given an ordered pair of states, what process may have occurred? (3) Given an ordered pair of states and a process, in what states must the two objects have been in between?
This work was partially funded by grants from Intergraph Corporation. Additional support from NSF for the NCGIA under grant number SES 88-10917 is gratefully acknowledged.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Alexandroff, 1961. Elementary Concepts of Topology. Dover Publications, Inc., New York, NY.
K. Al-Taha and A. Frank, 1991. Temporal GIS Keeps Data Current. 1991–1992 International GIS Source Book, 384–388.
J. Allen, 1983. Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 26(11):832–843.
L. Buisson, 1989. Reasoning on Space with Object-Centered Knowledge Representations. In: A. Buchmann, O. Günther, T. Smith, and Y. Wang, editors, Symposium on the Design and Implementation of Large Spatial Databases, Lecture Notes in Computer Science, Vol. 409, pages 325–344, Springer-Verlag, New York, NY.
S.K. Chang, E. Jungert, and Y. Li, 1989. The Design of Pictorial Databases Based Upon the Theory of Symbolic Projections. In: A. Buchmann, O. Günther, T. Smith, and Y. Wang, editors, Symposium on the Design and Implementation of Large Spatial Databases, Lecture Notes in Computer Science, Vol. 409, pages 303–323, Springer-Verlag, New York, NY.
S.K. Chang, Q.Y. Shi, and C.W., Yan, 1987. Iconic Indexing by 2-D Strings. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-9(6):413–428.
W. Chase and M. Chi, 1981. Cognitive Skill: Implications for Spatial Skill in Large-Scale Environment. In: J. Harvey, editor, Cognition, Social Behavior, and the Environment, pages 111–136, Lawrence Erlbaum Associates, Hillsdale, NJ.
J. De Kleer and J. Brown, 1984. A Qualitative Physics Based on Confluences. Artificial Intelligence, 24:7–83.
S. Dutta, 1989. Qualitative Spatial Reasoning: A Semi-Quantitative Approach Using Fuzzy Logic. In: A. Buchmann, O. Günther, T. Smith, and Y. Wang, editors, Symposium on the Design and Implementation of Large Spatial Databases, Lecture Notes in Computer Science, Vol. 409, pages 345–364, Springer-Verlag, New York, NY.
S. Dutta, 1991. Topological Constraints: A Representational Framework for Approximate Spatial and Temporal Reasoning. In: O. Günther and H.-J. Schek, editors, Advances in Spatial Databases—Second Symposium, SSD '91, Lecture Notes in Computer Science, Vol. 525, pages 161–180, Springer-Verlag, New York, NY.
M. Egenhofer, 1991. Reasoning about Binary Topological Relations. In: O. Günther and H.-J. Schek, editors, Advances in Spatial Databases—Second Symposium, SSD '91, Lecture Notes in Computer Science, Vol. 525, pages 143–160, Springer-Verlag, New York, NY.
M. Egenhofer and R. Franzosa, 1991. Point-Set Topological Spatial Relations. International Journal of Geographical Information Systems, 5(2):161–174.
M. Egenhofer and J. Herring, 1990. A Mathematical Framework for the Definition of Topological Relationships. In: K. Brassel and H. Kishimoto, editors, Fourth International Symposium on Spatial Data Handling, pages 803–813, Zurich, Switzerland.
M. Egenhofer and J. Herring, 1992. Categorizing Binary Topological Relationships Between Regions, Lines, and Points in Geographic Databases. Technical Report, Department of Surveying Engineering, University of Maine, Orono, ME.
B. Faltings, 1990. Qualitative Kinematics in Mechanisms. Artificial Intelligence, 44:89–119.
K. Forbus, P. Nielsen, and B. Faltings, 1991. Qualitative Spatial Reasoning: The CLOCK Project. Artificial Intelligence, 51:417–471.
A. Frank, 1991. Qualitative Spatial Reasoning about Cardinal Directions. In: Autocarto 10, pages 148–167, Baltimore, MD.
C. Freksa, 1992. Temporal Reasoning Based on Semi-Intervals. Artificial Intelligence, 54(1–2):199–227.
P. Hayes, 1978. The Naive Physics Manifesto. In: D. Michie, editor, Expert Systems in the Microelectronic Age, pages 242–270, Edinburgh University Press, Edinburgh, Scotland.
D. Hernández, 1991. Relative Representation of Spatial Knowledge: The 2-D Case. In: D. Mark and A. Frank, editors, Cognitive and Linguistic Aspects of Geographic Space, Kluwer Academic Publishers, Dordrecht.
J. Herring, 1991. The Mathematical Modeling of Spatial and Non-Spatial Information in Geographic Information Systems. In: D. Mark and A. Frank, editors, Cognitive and Linguistic Aspects of Geographic Space, pages 313–350, Kluwer Academic Publishers, Dordrecht.
G. Hunter and I. Wiliamson, 1990. The Development of a Historical Digital Cadastral Database. International Journal of Geographical Information Systems, 4(2):169–179.
D.J. Peuquet and Z. Ci-Xiang, 1987. An Algorithm to Determine the Directional Relationship Between Arbitrarily-Shaped Polygons in the Plane. Pattern Recognition, 20(1):65–74.
S. Pigot, 1991. Topological Models for 3D Spatial Information Systems. In: Autocarto 10, pages 368–392, Baltimore, MD.
R. Reiter, 1984. Towards a Logical Reconstruction of Relational Database Theory. In: M. Brodie, J. Mylopoulos, and J. Schmidt, editors, On Conceptual Modelling, pages 191–233, Springer-Verlag, New York, NY.
E. Spanier, 1966. Algebraic Topology. McGraw-Hill Book Company, New York, NY.
S. Stevens, 1946. On the Theory of Scales of Measurement. Science Magazine, 103(2684):677–680.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Egenhofer, M.J., Al-Taha, K.K. (1992). Reasoning about gradual changes of topological relationships. In: Frank, A.U., Campari, I., Formentini, U. (eds) Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Lecture Notes in Computer Science, vol 639. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55966-3_12
Download citation
DOI: https://doi.org/10.1007/3-540-55966-3_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55966-5
Online ISBN: 978-3-540-47333-6
eBook Packages: Springer Book Archive