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

Timothy M. Chan, Da Wei Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages1493-1511
Number of pages19
ISBN (Electronic)9781611977554
StatePublished - 2023
Externally publishedYes
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period1/22/231/25/23

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures'. Together they form a unique fingerprint.

Cite this