# 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.