| Title: |
Convexity Helps Iterated Search in 3D |
| Authors: |
Afshani, Peyman; Nekrich, Yakov; Staals, Frank; Sub Geometric Computing; Aichholzer, Oswin; Wang, Haitao |
| Publication Year: |
2025 |
| Subject Terms: |
Data structures; range searching; Software |
| Description: |
Inspired by the classical fractional cascading technique [13, 14], we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph G with bounded degree together with a set Hv of 3D hyperplanes associated with every vertex of v of G. The goal is to store the input such that given a query point q ∈ R3 and a connected subgraph H ⊂ G, we can decide if q is below or above the lower envelope of Hv for every v ∈ H. We show that using linear space, it is possible to answer queries in roughly O(log n +|H| √log n) time which improves trivial bound of O(|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 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 [15]. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/482983 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/482983 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.FD310F15 |
| Database: |
BASE |