Recomputation

When one point $p\in q.kNN$ moves farther from $q$ than $q.dist_k$ , CPM has to recompute all the $k$ NNs to reflect the update. To do that, CPM examines the cells recorded in the book-keeping information corresponding to $q$ (first processes the visit list and then the heap) till the new $k$ NNs are found. Though, those cells form the minimal set of cells required to be accessed during the initial $k$ NN computation, it is not necessary to access all of them in the update computation. For example, in the case where only the $k^{th}$ NN of $q$ moves farther from $q$ , we do not need to look into the previously accessed cells maintained in the visit list as the new $k^{th}$ NN must lie in the cells intersecting the circle with center $q$ and radius $q.dist_k$ only. Therefore, CPM is not optimal during the continuous monitoring.