hide
Free keywords:
-
Abstract:
Suppose we are given $n$ moving postmen described by
their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$,
where $s_i \in \R^2$ is the position of the $i$'th postman
at time $t=0$, and $v_i \in \R^2$ is his velocity.
The problem we address is how to preprocess the postmen data so as
to be able to efficientMailly answer two types of nearest neighbor queries.
The first one asks ``who is the nearest postman at time $t_q$ to a dog
located at point $s_q$. In the second type
a fast query dog is located a point $s_q$ at time $t_q$, its
velocity is $v_q$ where $v_q > |v_i|$ for all $i = 1,\ldots,n$, and we want
to know which postman the dog
can catch first. We present two solutions to these problems.
Both solutions use deterministic data structures.
