2026-07-20T10:41:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23155 2025-10-02T12:41:24Z ddc:004 open_access

Convexity Helps Iterated Search in 3D Afshani, Peyman Nekrich, Yakov Staals, Frank Data structures range searching Inspired by the classical fractional cascading technique [Bernard Chazelle and Leonidas J. Guibas, 1986; Bernard Chazelle and Leonidas J. Guibas, 1986], we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph 𝐆 with bounded degree together with a set H_v of 3D hyperplanes associated with every vertex of v of 𝐆. The goal is to store the input such that given a query point q ∈ ℝ³ and a connected subgraph 𝐇 ⊂ 𝐆, we can decide if q is below or above the lower envelope of H_v for every v ∈ 𝐇. We show that using linear space, it is possible to answer queries in roughly O(log n + |𝐇|√{log n}) time which improves trivial bound of O(|𝐇|log n) obtained by using planar point location data structures. Our data structure can in fact answer more general queries (it combines with shallow cuttings) and it even works when 𝐇 is given one vertex at a time. We show that this has a number of new applications and in particular, we give improved solutions to a set of natural data structure problems that up to our knowledge had not seen any improvements. We believe this is a very surprising result because obtaining similar results for the planar point location problem was known to be impossible [Chazelle and Liu, 2004]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peyman Afshani and Yakov Nekrich and Frank Staals 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.3 urn:nbn:de:0030-drops-231558 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.3 eng https://creativecommons.org/licenses/by/4.0/legalcode