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

Abstract

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.