Farthest Neighbor Queries

Given a set of points $P$ and a query point $q$ , a $k$ farthest neighbor query is to find a result set $R$ which contains $k$ objects such that for any $p\in (P-R)$ and for any $p'\in R$ , $dist(p',q)\geq dist(p,q)$ . The continuous monitoring of $k$ farthest neighbors ($k$ FN) is to continuously update the results affected by the movement of query point $q$ and data points $p\in P$ .

Farthest neighbor queries have various applications. A farthest neighbor query $q$ determines the minimum radius of the circle centered at $q$ which will cover all the data points in $P$ . Similarly, a $k$ farthest neighbors query can be issued to find the minimum radius of the circle around $q$ so that only $k-1$ points lie outside the circle. Consider another application where a team of commandos is on a mission and the leader wants that no member of the team is more than 10km away from him. Clearly, the members who are farther from him needs more of his attention. He might be interested in $k$ farthest team members so that he can monitor their activities and can advise them not to move too far from him.

Figure: Computation of a Farthest Nearest Neighbor Query

[A farthest neighbor query] [$p_3$ is the farthest neighbor]