Minimizing co-location potential for moving points

David Kirkpatrick, University of British Columbia

April 19, 2016

Imagine a collection of entities that move in d-dimensional space each with some (known but possibly different) bound on their speed. If we know the location of an individual entity at a particular time then its location lies in a region of uncertainty at all subsequent times. We consider the problem of minimizing the ply of the uncertainty regions (defined as the maximum, over all points p in the space, of the number of uncertainty regions that contain p) by means of queries to individual entities that are restricted to one query per unit of time. This notion of co-location potential is studied in two settings, one where ply is measured at some fixed time in the future, and the other where ply is measured continuously (i.e. at all times). Competitive query strategies are described in terms of a notion of intrinsic ply (the minimum ply achievable by any query strategy, even one that knows the trajectories of all entities).

Based on joint work with Will Evans, Maarten Löffler, Frank Staals, and Daniel Busto.