Tight Bounds on the Stabbing Number of Spanning Trees in Euclidean Space
Report ID: TR-155-88Author: Chazelle, Bernard
Date: 1988-05-00
Pages: 15
Download Formats: |PDF|
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.