2026-07-21T03:11:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24462 2026-01-21T10:06:35Z ddc:004 open_access

Solutions to the Generalised Alibi Query in Moving Object Databases (Short Paper) Jansen, Arthur Kuijpers, Bart Convex geometry Semi-algebraic geometry Space-time prism Geographic information systems Quantifier elimination 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arthur Jansen and Bart Kuijpers 2025 Is Part Of LIPIcs, Volume 355, 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2025.16 urn:nbn:de:0030-drops-244622 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode