Algorithms to decide the generalised alibi query for space-time prisms with stationary activity time

Abstract

Space-time prisms provide a framework to model the uncertainty on the space-time location of a moving object between its measured space-time locations, based on a bound on the speed of the moving object. In this model, the generalised alibi query asks whether n moving objects, given by their respective measured space- time locations and speed bounds, may have met. An analytical solution for n = 2 to this problem was first given by Kuijpers et al. (Int J Geogr Inf Sci 25(2):293–322, 2011) and later geometric and algorithmic solutions were proposed for aribtrary finite n in Jansen and Kuijpers (Comput Geom 127:102159, 2025). In this paper, we extend the previous methods to space-time prisms that include “stationary activity time”. We propose solutions that work via the spatial projection as well as methods that use the temporal projection, using techniques from convex and semi-algebraic geometry. We also address variants of the alibi query where it is asked whether the n moving objects may have met at a spatial location or at given moment in time.