{"ID":2899239,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.01775","arxiv_id":"2507.01775","title":"A Deterministic Partition Tree and Applications","abstract":"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 \\ge 2$), we construct a data structure using $O(n)$ space and $O(n^{1+ε})$ preprocessing time, such that each query can be answered in $o(n^{1-1/d})$ time (specifically, $O(n^{1-1/d} / \\log^{Ω(1)} n)$ time), thereby breaking an $Ω(n^{1-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.","short_abstract":"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 \\ge 2$), we construct a data structure using $O(n)$ space and $O(n^{1+ε})$ prep...","url_abs":"https://arxiv.org/abs/2507.01775","url_pdf":"https://arxiv.org/pdf/2507.01775v1","authors":"[\"Haitao Wang\"]","published":"2025-07-02T15:00:59Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}