×

A generalized topological view of motion in discrete space. (English) Zbl 1105.68103

From the introduction: In several areas of computer science, one is interested in using abstract mathematical structures as a basis for modelling certain phenomena of the real world. This interest is particularly strong in the knowledge representation subfield of artificial intelligence (AI), and amongst the phenomena studied in this field, those concerned with time, space, motion, and change have enjoyed a special prominence over the last 20 years or so.
The standard approach to these phenomena in the natural sciences has always been to use the well-developed theory of functions over the real numbers as the most appropriate starting point.
Discrete phenomena have also been studied by researchers interested in formulating a systematic and rigorous theory of digital images. This work has proceeded largely in isolation from the AI work mentioned above, but in recent years a certain rapprochement between the two areas has arisen as a result of a number of researchers beginning to explore the common ground between them. In particular, it has become apparent that by generalizing certain topological notions it may be possible to provide a unifying framework within which all the disparate forms of discrete space that have engaged the attention of workers in these fields may be described.
In this paper, I make use of such a framework to investigate the possible forms that continuous motion may take in discrete spaces. This requires, of course, an exact definition of what is meant by continuity in generalized spaces where the standard topological notion is not immediately applicable. It also requires careful consideration of what should be meant by such terms as ‘positions’, ‘distance’, ‘path’, and ‘time’ in the context of structures, defined purely mathematically.
I begin by establishing the general framework of closure spaces, which were introduced by E. Čech and subsequently suggested by M. B. Smyth [Theor. Comput. Sci. 151, 257–276 (1995; Zbl 0872.54003)] as an appropriate vehicle for the unification of disparate approaches to discrete space – notably the graph-theoretical approaches of the ‘digital topologies’ [T. Y. Kong and A. Rosenfeld, Comput. Vis. Graph. Image Process. 48, 357–393 (1989)] and the topological approach of [E. Khalimsky, R. Kopperman and P. R. Meyer, Topology Appl. 36, 1–17 (1990; Zbl 0709.54017); V. A. Kovalevsky, Comput. Vis. Graph. Image Process. 46, 141–161 (1989)]. Many of the results we require here are mathematically rather straightforward and the proofs are accordingly omitted. Amongst the closure spaces I identify two classes as being of particular interest, those which I call adjacency spaces and incidence spaces; both these types of structure have a property called quasi-discreteness which captures the discreteness of the intended models. I then investigate functions of closure spaces with a view to modelling motion, the motion of an object being specified by the function giving its position at each time; this requires, of course, a decision as to how time should be modelled, whether as a closure space itself or in the usual way in terms of \(\mathbb R\). This in turn impacts on the nature of continuity and I investigate systematically what continuous motion looks like in various combinations of choices for the modelling of space and time, both for the motion of point objects and for the motion of extended objects, whose positions are regions of space rather than points.

MSC:

68T30 Knowledge representation
54A99 Generalities in topology
68U10 Computing methodologies for image processing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Ahronovitz, J.-P. Aubert, C. Fiorio, The star-topology: a topology for image analysis, in: Discrete Geometry for Computer Imagery, Groupe GDR PRC/AMI du CNRS, 1995, pp. 107-116.; E. Ahronovitz, J.-P. Aubert, C. Fiorio, The star-topology: a topology for image analysis, in: Discrete Geometry for Computer Imagery, Groupe GDR PRC/AMI du CNRS, 1995, pp. 107-116.
[2] Allen, J., Towards a general theory of action and time, Artif. Intell., 23, 123-154 (1984) · Zbl 0567.68025
[3] E. Čech, Topological Spaces, Wiley, Chichester, 1966 (revised edition by Zdeněk Frolı́k and Miroslav Katětov).; E. Čech, Topological Spaces, Wiley, Chichester, 1966 (revised edition by Zdeněk Frolı́k and Miroslav Katětov). · Zbl 0141.39401
[4] Davis, E., Representations of Commonsense Knowledge (1990), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[5] E. Davis, Continuous shape transformation and metrics on regions, Funda. Inform. 46 (2001) 31-54.; E. Davis, Continuous shape transformation and metrics on regions, Funda. Inform. 46 (2001) 31-54. · Zbl 0974.68224
[6] Egenhofer, M. J.; Sharma, J., Topological relations between regions in \(R^2 and Z^2\), (Abel, D.; Ooi, B. C., Advances in Spatial Databases—3rd Internat. Symp. on Large Spatial Databases SSD’93. Advances in Spatial Databases—3rd Internat. Symp. on Large Spatial Databases SSD’93, Lecture Notes in Computer Science, Vol. 692 (1993), Springer: Springer New York), 316-336
[7] Galton, A. P., Towards an integrated logic of space, time, and motion, (Bajcsy, R., Proc. 13th Internat. Joint Conf. on Artificial Intelligence (IJCAI’93) (1993), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 1550-1555
[8] Galton, A. P., Continuous change in spatial regions, (Hirtle, S. C.; Frank, A. U., Spatial Information Theory: A Theoretical Basis for GIS. Spatial Information Theory: A Theoretical Basis for GIS, Lecture Notes in Computer Science, Vol. 1329 (1997), Springer: Springer New York), 1-13, (Proc. Internat. Conf. COSIT’97)
[9] Galton, A. P., The mereotopology of discrete space, (Freksa, C.; Mark, D. M., Spatial Information Theory: Cognitive and Computational Foundations of Geographic Science (1999), Springer: Springer New York), 251-266, (Proc. Internat. Conf. COSIT’99)
[10] Galton, A. P., Continuous motion in discrete space, (Cohn, A. G.; Giunchiglia, F.; Selman, B., Proc. 7th Internat. Conf. on Principles of Knowledge Representation and Reasoning (KR2000) (2000), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 26-37
[11] Galton, A. P., Qualitative Spatial Change (2000), Oxford University Press: Oxford University Press Oxford
[12] Khalimsky, E.; Kopperman, R.; Meyer, P. R., Computer graphics and connected topologies on finite ordered sets, Topology Appl., 36, 1-17 (1990) · Zbl 0709.54017
[13] Kong, T. Y.; Rosenfeld, A., Digital topologyintroduction and survey, Comput. Vision Graphics Image Process., 48, 357-393 (1989)
[14] Kovalevsky, V. A., Finite topology as applied to image analysis, Comput. Vision Graphics Image Process., 46, 141-161 (1989)
[15] Kovalevsky, V. A., A new concept for digital geometry, (Ying-Lie, O.; Toet, A.; Foster, D.; Heijmans, H. J.A. M.; Meer, P., Shape in Picture: Mathematical Description of Shape in Grey-level Images. Shape in Picture: Mathematical Description of Shape in Grey-level Images, NATO Advanced Science Institutes Series, Vol. 126 (1993), Springer: Springer Berlin), 37-51
[16] Randell, D. A.; Cui, Z.; Cohn, A. G., A spatial logic based on regions and connection, (Nebel, B.; Rich, C.; Swartout, W., Principles of Knowledge Representation and Reasoning: Proc. 3rd Internat. Conf. (KR’92) (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 165-176
[17] Smyth, M. B., Semi-metrics, closure spaces and digital topology, Theoret. Comput. Sci., 151, 257-276 (1995) · Zbl 0872.54003
[18] O. Stock (Ed.), Spatial and Temporal Reasoning, Kluwer Academic Publishers, Dordrecht, 1997.; O. Stock (Ed.), Spatial and Temporal Reasoning, Kluwer Academic Publishers, Dordrecht, 1997.
[19] Winter, S., Topological relations between discrete regions, (Egenhofer, M. J.; Herring, J. R., Advances in Spatial Databases (1995), Springer: Springer Berlin), 310-327
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.