Technique

The continuous monitoring of donut-region $k$ CNN queries is exactly same as the continuous monitoring of $k$ NN queries with the only difference that the distance of any object $p$ that lies outside the range is considered infinity and the starting radius of CircularTrip is set as $d_L$ . Consider the example of Fig. , where a 1-CNN query $q$ is issued with distance bounded by $d_L$ and $d_U$ . The algorithm starts by calling the CircularTrip with radius set as $d_L$ and then increases it by $\delta$ everytime unless $k$ NNs are found. Algorithm finds $p_2$ which is reported as answer. Algorithm visits only the cells that are shown shaded in Fig. . Note that, this is the minimal set of cells that is required to be visited in order to guarantee the correctness.

Figure: Computation of a Donut-Region $1$ -CNN Query

The continuous monitoring of $k$ CNN is similar to the monitoring of simple $k$ NN queries. Note that simple $k$ NN queries can be considered a special case of donut-region $k$ CNN queries with $d_L=0$ and $d_U=\infty$ .