Collision Detection Queries on moving objects with uncertain velocity

A new type of the spatio-temporal queries is the Collision Detection Query (CDQ for short). In this paper, we focus on efficiently processing the CDQ on moving objects with uncertainty. Given two sets O and Q of objects, each of which moves with uncertain speed and direction, and a time instant t, the CDQ returns each pair of objects (o, q) (where o ∈ O and q ∈ Q), such that o is possible to collide with q at time t. The pairs of objects satisfying the CDQ are termed the collision-possible pairs (or CPPs for short). We first utilize the R^lsd-tree, in which the spatially proximate objects with similar uncertain speeds and directions are grouped together, to effectively manage the moving objects in O and Q. Then, with the two R^lsd-trees for O and Q, we develop the specialized index traversals combined with three pruning criteria, the location-pruning criterion, the angle-pruning criterion, and the speed-pruning criterion to efficiently determine the objects that may collide with each other.