Solutions to the Generalised Alibi Query in Moving Object Databases (Short Paper)

Abstract

Space-time prisms provide a framework to model the uncertainty on the space-time points that a moving object may have visited between measured space-time locations, provided that a bound on the speed of the moving object is given. In this model, the alibi query asks whether two moving objects, given by their respective measured space-time locations and speed bound, may have met. An analytical solution to this problem was first given by Othman [Kuijpers et al., 2011]. In this paper, we address the generalised alibi query that asks the same question for an arbitrary number 𝗇 ≥ 2 of moving objects. We provide several solutions (mainly via the spatial and temporal projection) to this query with varying time complexities. These algorithmic solutions rely on techniques from convex and semi-algebraic geometry. We also address variants of the generalised alibi query where the question is asked for a given spatial location or a given moment in time.