Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Chan, Timothy M.; Nekrich, Yakov; Rahul, Saladi; Tsakalidis, Konstantinos http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-90352
URL:

; ; ;

Orthogonal Point Location and Rectangle Stabbing Queries in 3-d

pdf-format:


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(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.

BibTeX - Entry

@InProceedings{chan_et_al:LIPIcs:2018:9035,
  author =	{Timothy M. Chan and Yakov Nekrich and Saladi Rahul and Konstantinos Tsakalidis},
  title =	{{Orthogonal Point Location and Rectangle Stabbing Queries in 3-d}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9035},
  URN =		{urn:nbn:de:0030-drops-90352},
  doi =		{10.4230/LIPIcs.ICALP.2018.31},
  annote =	{Keywords: geometric data structures, orthogonal point location, rectangle stabbing, pointer machines, I/O model, word RAM model}
}

Keywords: geometric data structures, orthogonal point location, rectangle stabbing, pointer machines, I/O model, word RAM model
Seminar: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI