Orthogonal point location and rectangle stabbing queries in 3-d

Timothy M. Chan, Yakov Nekrich, Saladi Rahul, Konstantinos Tsakalidis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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 log3/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(logw n + 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.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
DOIs
StatePublished - Jul 1 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume107
ISSN (Print)1868-8969

Other

Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
CountryCzech Republic
CityPrague
Period7/9/187/13/18

Keywords

  • Geometric data structures
  • I/O model
  • Orthogonal point location
  • Pointer machines
  • Rectangle stabbing
  • Word RAM model

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Orthogonal point location and rectangle stabbing queries in 3-d'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M., Nekrich, Y., Rahul, S., & Tsakalidis, K. (2018). Orthogonal point location and rectangle stabbing queries in 3-d. In C. Kaklamanis, D. Marx, I. Chatzigiannakis, & D. Sannella (Eds.), 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 [31] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 107). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2018.31