Geometric and algorithmic solutions to the generalised alibi query

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 spacetime locations and speed bound, may have met. An analytical solution to this problem was first given by Othman [15]. In this paper, we address the generalised alibi query that asks the same question for an arbitrary number n >= 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 semialgebraic 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. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.