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.


slides
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