Continuous Pie-Region $k$ CNN queries

As defined earlier, a continuous pie-region $k$ CNN query $q$ with the angle bounds $\langle \theta_1,\theta_2 \rangle$ is to find $k$ nearest neighbors among a set of points $P'\subseteq P$ such that all points in $P'$ lie within the angle range $\langle \theta_1,\theta_2 \rangle$ . Such $k$ CNN queries have many applications. Consider, for example, a user might be interested in only the points that are in north-east. In this case a query with angle range $\langle 90^\circ,180^\circ \rangle$ will be issued.

Recall that in order to continuously monitor reverse nearest neighbors, six continuous CNN queries are issued [XZ06] as discussed in Section . Each continuous CNN query monitors the nearest neighbors in its region that covers an angle range of $60^\circ$ degrees as shown in Fig. . The algorithm needs to continuously monitor nearest neighbors in the six constrained regions from $S_0$ to $S_5$ . Continuous CNN query that monitors constrained region $S_1$ can be denoted as $q_{\langle 60^\circ,120^\circ \rangle}$ because it monitors the nearest neighbors in the region that is bounded by the angle range $\langle 60^\circ$ , $120^\circ\rangle$ .

Figure: Six Pie-Region Constrained NN Queries