2026-08-17T09:39:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24583 2025-12-16T14:01:08Z ddc:004 open_access

A Deterministic Partition Tree and Applications Wang, Haitao partition trees simplex range searching segment intersection queries ray-shootings multi-level data structures 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(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.114 urn:nbn:de:0030-drops-245836 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.114 eng https://creativecommons.org/licenses/by/4.0/legalcode