Orthogonal range reporting and rectangle stabbing for fat rectangles

Timothy M. Chan, Yakov Nekrich, Michiel Smid

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

Abstract

In this paper we study two geometric data structure problems in the special case when input objects or queries are fat rectangles. We show that in this case a significant improvement compared to the general case can be achieved. We describe data structures that answer two- and three-dimensional orthogonal range reporting queries in the case when the query range is a fat rectangle. Our two-dimensional data structure uses O(n) words and supports queries in O(log log U+ k) time, where n is the number of points in the data structure, U is the size of the universe and k is the number of points in the query range. Our three-dimensional data structure needs O(nlog εU) words of space and answers queries in O(log log U+ k) time. We also consider the rectangle stabbing problem on a set of three-dimensional fat rectangles. Our data structure uses O(n) space and answers stabbing queries in O(log Ulog log U+ k) time.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
EditorsZachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack
PublisherSpringer-Verlag Berlin Heidelberg
Pages283-295
Number of pages13
ISBN (Print)9783030247652
DOIs
StatePublished - 2019
Event16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada
Duration: Aug 5 2019Aug 7 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11646 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Symposium on Algorithms and Data Structures, WADS 2019
CountryCanada
CityEdmonton
Period8/5/198/7/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Orthogonal range reporting and rectangle stabbing for fat rectangles'. Together they form a unique fingerprint.

Cite this