Chan, TM, Nekrich, Y, Rahul, S and Tsakalidis, K 
ORCID: 0000-0001-6470-9332
(2022)
ORTHOGONAL POINT LOCATION AND RECTANGLE STABBING QUERIES IN 3-D.
Journal of Computational Geometry, 13 (1).
pp. 399-428.
Abstract
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 sup- ports 3-d point location queries on n disjoint axis-aligned boxes with optimal O (log") query time in the (arithmetic) pointer machine model. This improves the previous 0 (\ogi/2 n^ bound of Rahul \SODA 201o|. 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 HAM model with sub-logarithmic query time. Our tech- nique also improves upon the result of de Berg, van Kreveld, and Snoeyink \ Journal of Algorithms I995| for 3-d point location in (space filling) box subdivisions: we obtain a linear-space data structure with G{\og2\ogU) 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(\ogwn 4- k) time in the word RAM model, where k is the number of rectangles reported and w is the number of bits in a word. We similarly obtain the first optimal data structure for the closely related problem of 2-d top-/: 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.
| Item Type: | Article |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 03 Mar 2023 08:53 |
| Last Modified: | 03 Mar 2023 09:12 |
| DOI: | 10.20382/jocg.v13i1a15 |
| Open Access URL: | https://doi.org/10.20382/jocg.v13i1a15 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3168715 |
Dimensions
Dimensions
