## Competitive Query Strategies for Minimising the Ply of the Potential Locations of Moving Points

We study the problem of maintaining the locations of a collection of *n* entities that are moving with some fixed upper bound on their speed. We assume a setting where we may query the current location of entities, but handling this query takes a certain unit of time, during which we cannot query any other entities. In this model, we can never know the exact locations of all entities at any one time. Instead, we maintain a representation of the potential locations of all entities. We measure the quality of this representation by its *ply*: the maximum number of entities that could potentially be at the same location.

Since the ply could be large for every query strategy, we analyse the performance of our algorithms in a competitive framework: we consider the worst case ratio of the ply achieved by our algorithms to the *intrinsic ply* (the smallest ply achievable by any algorithm, even one that knows in advance the full trajectories of all entities). We show that, if our goal is to mimimise the ply at some number *τ* of time units in the future, an *O*(1)-competitive algorithm exists, provided *τ* is sufficiently large. If *τ* is small and the *n* entities move in any constant dimension *d*, our algorithm is *O*((ℓ/*τ* + 1)^{d − d/(d + 1)})-competitive, where ℓ is the average time since the last query over all entities. We also provide matching lower bounds, and we show that computing the intrinsic ply exactly is NP-hard, even when the trajectories are known in advance.

keywords: Computational Geometry, Data Imprecision, Online Algorithms

### Conference Proceedings (peer-reviewed)

David Kirkpatrick, Frank Staals, Maarten Löffler, Will Evans

Competitive Query Strategies for Minimising the Ply of the Potential Locations of Moving Points

Proc. 29th Symposium on Computational Geometry

155–163, 2013

### Workshop or Poster (weakly reviewed)

David Kirkpatrick, Frank Staals, Maarten Löffler, Will Evans

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

Proc. 30th European Workshop on Computational Geometry

, 2014

back to list