TY - GEN

T1 - Simplex Range Searching Revisited

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

AU - Chan, Timothy M.

AU - Zheng, Da Wei

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - 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(nd) (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(nd polylog n) space. Previous data structures with similar space bounds by Matoušek from nearly three decades ago had O(logd+1 n) or O(logd+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(n1-1/d) time, and stabbing reporting queries in O(n1-1/d + k) time. Previous data structures had extra logd 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.

AB - 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(nd) (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(nd polylog n) space. Previous data structures with similar space bounds by Matoušek from nearly three decades ago had O(logd+1 n) or O(logd+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(n1-1/d) time, and stabbing reporting queries in O(n1-1/d + k) time. Previous data structures had extra logd 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.

UR - http://www.scopus.com/inward/record.url?scp=85170084986&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85170084986&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85170084986

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1493

EP - 1511

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

Y2 - 22 January 2023 through 25 January 2023

ER -