Modeling uncertainty of moving objects on road networks via space-time prisms

Moving objects produce trajectories, which are typically observed in a finite sample of time-stamped locations. Between sample points, we are uncertain about the moving objects's location. When we assume extra information about an object, for instance, a (possibly location-dependent) speed limit, we can use space-time prisms to model the uncertainty of an object's location. Until now, space-time prisms have been studied for unconstrained movement in the 2D plane. In this paper, we study space-time prisms for objects that are constrained to travel on a road network. Movement on a road network can be viewed as essentially one-dimensional. We describe the geometry of a space-time prism on a road network and give an algorithm to compute and visualize space-time prisms. For experiments and illustration, we have implemented this algorithm in MATHEMATICA. Furthermore, we study the alibi query, which asks whether two moving objects could have possibly met or not. This comes down to deciding if the chains of space-time prisms produced by these moving objects intersect. We give an efficient algorithm to answer the alibi query for moving objects on a road network. This algorithm also determines where and when two moving objects may have met.