โ Scribed by Bentley, Jon Louis
No coin nor oath required. For personal study only.
A K-d tree represents a set of N points in K-dimensional space. Operations on a semidynamic tree may delete and undelete points, but may not insert new points. 'ntis paper shows that several operations that require O(log N) expected time in general K-d trees may be performed in constant expected time in sernidynamic trees. These operations include deletion, undeletion, nearest neighbor searching, and fixed-radius near neighbor searching (the running times of the first two are proved, while the last two are supported by experiments and heuristic arguments). Other new techniques can also be applied to general K-d trees: simple sampling reduces the time to build a tree from O(KN log N) to O(KN + N log N), and more advanced sampling builds a robust tree in the same time. The methods are straightforward to implement, and lead to a data structure that is sigrfifieently faster and less vulnerable to pathological inputs than ordinary K-d trees.
Introduction
A K-dimensional binary search tree (abbreviated K-d tree) represents a set of points in K-dimensional space. Many kinds of searches can be performed on a K-d tree, including exact-match, partial-match, and range queries. The discussion of K.d trees in many textbooks concentrates on these query types, which are important in database applications (see, for instance, Mehlhorn [1984, Section 2.1], Shames [1985, Section 2.3.2], and Sedgewick [1988, Chapter 26]). This paper is concerned with K-d t~ees that support two kinds of proximity queries:Nearest neighbor qtw, y. Report the nearest neighbor to a given query point, under a specified metric.Fixed-radius near neighbor query. Report all points within a fixed radius of the given query point, under a specified metric.
๐ SIMILAR VOLUMES
We consider the following problem, known as simplex range searching: Preprocess a set P of n points in ~d SO that, given any query simplex q, the points in P n q can be counted or r e p o r t e d efficiently. We can put the m a n y variants of this problem under the same umbrella by assuming a weigh