We introduce a new, simple method for answering reverse and nearest neighbor queries for moving objects, e.g., mobile players in a multiplayer game, where a trajectory is known to the system for each object, at least in the short-term. See [Rahmati 2014].

This paper presents a kinetic data structure (KDS) for solutions to the all nearest neighbors problem and the closest pair problem in the plane. For a set P of n moving points where the trajectory of each point is an algebraic function of constant maximum degree s, our kinetic algorithm uses O(n) space and O(n log n) preprocessing time, and processes O(n2β22s+2(n)log n) events with total processing time O(n2β22s+2(n)log2 n), where βs(n) is an extremely slow-growing function. In terms of the KDS performance criteria, our KDS is efficient, responsive (in an amortized sense), and compact.