Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures

We revisit the classic problem of simplex range searching and related problems in computational geometry. We present a collection of new results which improve previous bounds by multiple logarithmic factors that were caused by the use of multi-level data structures. Highlights include the following:

• For a set of n points in a constant dimension d, we give data structures with O(n d ) (or slightly better) space that can answer simplex range counting queries in optimal O(log n) time and simplex range reporting queries in optimal O(log n + k) time, where k denotes the output size. For semigroup range searching, we obtain O(log n) query time with O(n d polylog n) space. Previous data structures with similar space bounds by Matoušek from nearly three decades ago had O(log d+1 n) or O(log d+1 n + k) query time.

• For a set of n simplices in a constant dimension d, we give data structures with O(n) space that can answer stabbing counting queries (counting the number of simplices containing a query point) in O(n 1-1/d ) time, and stabbing reporting queries in O(n 1-1/d +k) time. Previous data structures had extra log d n factors in space and query time.

• For a set of n (possibly intersecting) line segments in 2D, we give a data structure with O(n) space that can answer ray shooting queries in O( √ n) time. This improves Wang's recent data structure [SoCG'20] with O(n log n) space and O( √ n log n) query time.