2026-07-23T00:12:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9035 2024-03-06T10:43:12Z ddc:004 open_access

Orthogonal Point Location and Rectangle Stabbing Queries in 3-d Chan, Timothy M. Nekrich, Yakov Rahul, Saladi Tsakalidis, Konstantinos geometric data structures orthogonal point location rectangle stabbing pointer machines I/O model word RAM model In this work, we present a collection of new results on two fundamental problems in geometric data structures: orthogonal point location and rectangle stabbing. - Orthogonal point location. We give the first linear-space data structure that supports 3-d point location queries on n disjoint axis-aligned boxes with optimal O(log n) query time in the (arithmetic) pointer machine model. This improves the previous O(log^{3/2} n) bound of Rahul [SODA 2015]. We similarly obtain the first linear-space data structure in the I/O model with optimal query cost, and also the first linear-space data structure in the word RAM model with sub-logarithmic query time. - Rectangle stabbing. We give the first linear-space data structure that supports 3-d 4-sided and 5-sided rectangle stabbing queries in optimal O(log_wn+k) time in the word RAM model. We similarly obtain the first optimal data structure for the closely related problem of 2-d top-k rectangle stabbing in the word RAM model, and also improved results for 3-d 6-sided rectangle stabbing. For point location, our solution is simpler than previous methods, and is based on an interesting variant of the van Emde Boas recursion, applied in a round-robin fashion over the dimensions, combined with bit-packing techniques. For rectangle stabbing, our solution is a variant of Alstrup, Brodal, and Rauhe's grid-based recursive technique (FOCS 2000), combined with a number of new ideas. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Yakov Nekrich and Saladi Rahul and Konstantinos Tsakalidis 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.31 urn:nbn:de:0030-drops-90352 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.31 eng https://creativecommons.org/licenses/by/3.0/legalcode