Tight Bounds on the Stabbing Number of Spanning Trees in Euclidean Space

Abstract:

We tighten the analysis of a data structure for simplex range searching discovered recently by Welzl. Our main result is that any set of n points in Ed admits a spanning tree which cannot be cut by any hyperplane (or hypersphere) through more than roughly n1-1/d edges. This result yields quasi-optimal
solutions to simplex range searching in the arithmetic model of computation. We also look at circular and polygonal range searching on a random access machine. Given n points in E2, we derive a data structure of size O(n log n) for counting how many points fall inside a query convex k-gon (for arbitrary
values of k). The query is O(sqrt kn log n). If k is fixed once and for all (as in triangular range searching) then the storage requirement drops to O(n). We also describe an O(n log n)-size data structure for counting how many points fall inside a query circle in O(sqrt n log2 n) query time.