2025/07/02 by Wang, Haitao
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.01775
In this paper, we present a deterministic variant of Chan's randomized partition tree [Discret. Comput. Geom., 2012]. This result leads to numerous applications. In particular, for d-dimensional simplex range counting (for any constant d ≥ 2), we construct a data structure using O(n) space and O(n1+ε) preprocessing time, such that each query can be answered in o(n1-1/d) time (specifically, O(n1-1/d / logΩ(1) n) time), thereby breaking an Ω(n1-1/d) lower bound known for the semigroup setting. Notably, our approach does not rely on any bit-packing techniques. We also obtain deterministic improvements for several other classical problems, including simplex range stabbing counting and reporting, segment intersection detection, counting and reporting, ray-shooting among segments, and more. Similar to Chan's original randomized partition tree, we expect that additional applications will emerge in the future, especially in situations where deterministic results are preferred.