This chapter discusses the use of transition graphs for reasoning about continuous spatial change over time. The chapter first presents a general definition of a transition graph for a partition of a topological space. Then it defines the path-connected and the homogeneous refinements of such a partition. The qualitative behavior of paths through the space corresponds to the structure of paths through the associated transition graphs, and of associated interval label sequences, and the authors prove a number of metalogical theorems that characterize these correspondences in terms of the expressivity of associated first-order languages. They then turn to specific real-world problems and show how this theory can be applied to domains such as rigid objects, strings, and liquids.
Top1. Introduction
Many spatial aspects of many persistent entities vary continuously over time: the direction of a weather vane, the length of a rubber band; the shape of a balloon and so on. Many others, of course, do not: the territory of the United States, the shape of a shadow on a surface, the shape of a tree when a limb is pruned. However, when it is known that a spatial entity does change continuously, that constraint can be very useful in reasoning about its behavior over time.
Consider the following inferences:
- A.
Two interlocked jigsaw puzzle pieces cannot be separated by a movement in the plane of the puzzle, but can be separated by lifting one perpendicular to the plane.
- B.
Consider a string loop of length L wrapped once around the waist of an hourglass with spherical globes of circumference C. If L>C then the loop can be removed from the hourglass without coming into contact with the hourglass and without ever being taut. If L<C, then the loop cannot be removed from the hourglass. If L=C, then the loop can be removed from the hourglass, but at some point it must be in contact with the hourglass, and it must be taut. It can be taken off either the upper or the lower globe.
If the globes of the hourglass are long cylinders, the circular cross section has circumference C, and C=L, then the string can be removed from the hourglass, but it will be taut and in contact with the hourglass over an extended interval of time.
If, instead of a string loop, we have a rubber band whose length is less than C at rest but can be stretched to a length greater than C, then it can be removed from the hourglass without being in contact with the hourglass, but it must be stretched in order to do so.
- C.
A quantity of milk in a closed bottle remains in the bottle. If at time T1 there is milk sitting in cup A, and at a later time T2 this milk has moved to a cup B, and both cups are stationary, then the milk came out of the top of cup A and went in the top of cup B.
- D.
The dog can go from the dining room into the kitchen. However, if a chair is placed in the middle of the kitchen doorway, then the dog cannot go from the dining room to the kitchen. If the chair is placed at the edge of the doorway, then the dog can squeeze past and get into the kitchen.
- E.
A person who is in Canada at one time and in the United States at a later time must cross the U.S. border at some time in between. A person who is in Alaska at one time and in Idaho at a later time must cross the U.S. border at least twice in between. It is possible to travel from any point in Idaho to any point in Ohio without crossing the border of the United States. This seems like the simplest of these inferences; in fact, however, it is the example for which the theory we develop in this chapter is least adequate.
A number of points may be observed about these examples. First, both the givens and the conclusions are qualitative; no precise measurements or shape descriptions are given. Second, they depend on continuity: If Star Trek style teleportation were available, the inferences would not be valid. For that matter, analogous inference can fail if they involved entities that change discontinuously; for instance, when the Louisiana Purchase took effect in 1803, many objects went from being far from the United States to being deep inside the United States without ever being on the border. Third, many of the sample inferences above depend on further physical limitations on the dynamic spatial behaviors of the objects involved in addition to continuity.
Moreover, the well-known scheme for representing qualitative spatial change in terms of transitions between RCC relations is inadequate to justify or represent these inferences. In that theory, as we will discuss in greater detail in section 2, the relation between two regions is characterized in terms of eight possible mereotopological relations. Spatial change over time is characterized in terms of the sequence of the evolving sequence of these relations. Continuity is characterized in terms of possible and impossible transitions from one relation to another, as illustrated in the well known graph in Figure 1.
Figure 1. Transition graph for RCC relations