Towards Tight Lower Bounds for Range Reporting on the RAM

Allan Grønlund, Kasper Green Larsen

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearch

2 Citations (Scopus)

Abstract

In the orthogonal range reporting problem, we are to preprocess a set of n points with integer coordinates on a U × U grid. The goal is to support reporting all k points inside an axis-aligned query rectangle. This is one of the most fundamental data structure problems in databases and computational geometry. Despite the importance of the problem its complexity remains unresolved in the word-RAM. On the upper bound side, three best tradeoffs exist, all derived by reducing range reporting to a ball-inheritance problem. Ball-inheritance is a problem that essentially encapsulates all previous attempts at solving range reporting in the word-RAM. In this paper we make progress towards closing the gap between the upper and lower bounds for range reporting by proving cell probe lower bounds for ball-inheritance. Our lower bounds are tight for a large range of parameters, excluding any further progress for range reporting using the ball-inheritance reduction.

Original languageEnglish
Book seriesLeibniz International Proceedings in Informatics
Volume55
Pages (from-to)92:1 - 92:12
Number of pages12
ISSN1868-8969
DOIs
Publication statusPublished - 1 Aug 2016
EventICALP 2016 : 43RD INTERNATIONAL COLLOQUIUM ON AUTOMATA, LANGUAGES, AND PROGRAMMING - Rome, Italy
Duration: 12 Jul 201615 Jul 2016
http://www.easyconferences.eu/icalp2016/index.html

Conference

ConferenceICALP 2016
Country/TerritoryItaly
CityRome
Period12/07/201615/07/2016
Internet address

Keywords

  • Cell probe model
  • Data structures
  • Lower bounds
  • Range reporting

Fingerprint

Dive into the research topics of 'Towards Tight Lower Bounds for Range Reporting on the RAM'. Together they form a unique fingerprint.

Cite this