Query Strategies for Minimizing the Ply of the Potential Locations of Entities Moving with Different Speeds

In a recent paper [2] we gave query strategies for minimizing
the ply of the potential locations of a set of
moving entities. We extend our results to the case
where the entities have dierent maximum speeds.
We present a query strategy that can achieve ply
O(k) when we have at least 2n time, the intrinsic
ply of the entities is , and the speeds of the entities
fall into k speed classes. Furthermore, we show that
for every query strategy there is a set of n entities for
which the strategy achieves ply
(k). Hence, our
results are optimal up to a constant factor.
We present our query strategy for entities moving in
R1. However, our results extend to higher dimensions.