Abstract

Inspired by the classical fractional cascading technique , we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph \(\mathbf{G}\) with bounded degree together with a set \(H_v\) of 3D hyperplanes associated with every vertex of \(v\) of \(\mathbf{G}\). The goal is to store the input such that given a query point \(q\in \R^3\) and a connected subgraph \(\mathbf{H}\subset \mathbf{G}\), we can decide if \(q\) is below or above the lower envelope of \(H_v\) for every \(v\in \mathbf{H}\). We show that using linear space, it is possible to answer queries in roughly \(O(\log n + |\mathbf{H}|\sqrt{\log n})\) time which improves trivial bound of \(O(|\mathbf{H}|\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 \(\mathbf{H}\) 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 .

Corresponding Publications

Convexity Helps Iterated Search in 3D

Peyman Afshani, Yakov Nekrich, Frank Staals

Proc. 41th Annual Symposium on Computational Geometry, 2025

Invited for a Special Issue on SoCG 2025 in JoCG

Download Local Copy View Slides Export Citation

@inproceedings{convexityHelps3d2025,
  author = {Afshani, Peyman and Nekrich, Yakov and Staals, Frank},
  title = {Convexity Helps Iterated Search in 3D},
  booktitle = {Proc. 41th Annual Symposium on Computational Geometry},
  year = {2025},
  location = {Kanazawa Japan},
  keywords = {data structure, range searching, fractional cascading},
  category = {datastructures},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.SoCG.2025.3},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2025.3},
  note = {Invited for a Special Issue on SoCG 2025 in JoCG},
}