Back to Nearest neighbors searching
A semi-dynamic point-set is a function .
A semi-dynamic point-set is a time-varying finite point-set whose points are drawn from . At each time instant some of the points are (possibly) removed and some are inserted. Usually, when talking about semi-dynamic point-sets, one assumes that only a small part of the active set is changed at each time instant, i.e., that there is some temporal coherence. This assumption allows to think of more efficient algorithms for this specific case.
The problem is to search for nearest neighbors in a semi-dynamic point set. An obvious way to do this is to repeat a standard nearest neighbor search from the stratch at each time instant. However, this is inefficient because the temporal coherence is not taken advantage of. Specifically to address this problem, Pastel implements the multi-level kd-tree, which maintains efficient searches and avoids reconstruction. Using this data structure, the problem is approached by constructing the kd-tree based on all points in . Then, at each time step, nearest neighbors are searched, and points are removed and inserted incrementally.