Initial Computation

Initial computation of $k$ farthest neighbors is very similar to the computation of nearest neighbors. The algorithm initially calls CircularTrip with radius set as $R$ where $R$ is the maximum distance of $q$ from the region in which the farthest neighbors are to be found. As opposed to nearest neighbor queries, the cells returned by CircularTrip are inserted in a heap according to their $maxdist$ from $q$ . The cells are visited in descending order of their $maxdist$ and the radius of CircularTrip is decreased by $\delta$ everytime. Let $q.dist_k$ be the distance between $q$ and $k^{th}$ farthest neighbor found so far, the algorithm stops when the radius of CircularTrip becomes smaller than or equal to $q.dist_k$ .