Efficient partition trees 论文

摘要

We prove a theorem on partitioning point sets in Ed (d fixed) and give an efficient construction of partition trees based on it. Such a partition tree for n points uses O(n) space, can be constructed in O(n log n) de-terministic time, and it can be used to answer simplex range queries (counting or general semigroup ones) in time O(nl–lld(log n) O[lJ). If we allow O(nl+d) pre-processing time, where 6 is some positive constant, a more complicated data structure yields query time O(nl-lld(loglog n) O(lJ). J?or dimensions d = 2,3 and if the weights of the points lie in a group, we get query time 0(nl-11d20(10g ” ‘)). This attains the lower bounds due to [Chazelle 89] upto polylogarithrnic factors, im-proving the results of [Chazelle et al. 90], making the preprocessing deterministic without loss of efficiency and simplifying the query answering algorithm. Dy-namization of our data structures and tradeoffs between preprocessing (and storage) and query time are also possible. The partition result is also applied for a deterministic computation of c-cuttings. E.g., given a collection of n lines in the plane and a parameter r < nl- $ for a fixed 6>0, the plane can be subdivided into O(r2) triangles, each intersected by at most n/r of the given lines, in time O(nl/2r3/2 + n log r), thus in almost linear time for r < n113. ●Part of thk research waa performed while the author was visiting at the Freie Universit5t Berlin.