Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
Timothy M. Chan, Da Wei Zheng · Society for Industrial and Applied Mathematics eBooks · 2023
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: