Output-Sensitive Tools for Range Searching in Higher Dimensions

Original · EN

Let P be a set of n points in Rᵈ. A point p ∈ P is k-shallow if it lies in a halfspace which contains at most k points of P (including p). We show that if all points of P are k-shallow, then P can be partitioned into Θ(n/k) subsets, so that any hyperplane crosses at most O((n/k)¹⁻¹/⁽ᵈ⁻¹⁾ ²/⁽ᵈ⁻¹⁾(n/k)) subsets. Given such a partition, we can apply the standard construction of a spanning tree with small crossing number within each subset, to obtain a spanning tree for the point set P, with crossing number O(n¹⁻¹/⁽ᵈ⁻¹⁾k¹/ᵈ⁽ᵈ⁻¹⁾ ²/⁽ᵈ⁻¹⁾(n/k)). This allows us to extend the construction of Har-Peled and Sharir hs11 to three and higher dimensions, to obtain, for any set of n points in Rᵈ (without the shallowness assumption), a spanning tree T with small relative crossing number. That is, any hyperplane which contains w ≤ n/2 points of P on one side, crosses O(n¹⁻¹/⁽ᵈ⁻¹⁾w¹/ᵈ⁽ᵈ⁻¹⁾ ²/⁽ᵈ⁻¹⁾(n/w)) edges of T. Using a similar mechanism, we also obtain a data structure for halfspace range counting, which uses O(n n) space (and somewhat higher preprocessing cost), and answers a query in time O(n¹⁻¹/⁽ᵈ⁻¹⁾k¹/ᵈ⁽ᵈ⁻¹⁾ ((n/k))ᵒ⁽¹⁾), where k is the output size.