Dynamic orthogonal range searching on the RAM, Revisited

Timothy M. Chan, Konstantinos Tsakalidis

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

Abstract

We study a longstanding problem in computational geometry: 2-d dynamic orthogonal range reporting. We present a new data structure achieving O(log n/log log n+k) optimal query time and O(log2/3+o(1)n) update time (amortized) in the word RAM model, where n is the number of data points and k is the output size. This is the first improvement in over 10 years of Mortensen's previous result [SIAM J. Comput., 2006], which has O (log7/8/ϵn) update time for an arbitrarily small constant ϵ. In the case of 3-sided queries, our update time reduces to O (log1/2+ϵn), improving Wilkinson's previous bound [ESA 2014] of O(log2/3+ϵ).

Original languageEnglish (US)
Title of host publication33rd International Symposium on Computational Geometry, SoCG 2017
EditorsMatthew J. Katz, Boris Aronov
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages281-2813
Number of pages2533
ISBN (Electronic)9783959770385
DOIs
StatePublished - Jun 1 2017
Event33rd International Symposium on Computational Geometry, SoCG 2017 - Brisbane, Australia
Duration: Jul 4 2017Jul 7 2017

Publication series

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

Other

Other33rd International Symposium on Computational Geometry, SoCG 2017
Country/TerritoryAustralia
CityBrisbane
Period7/4/177/7/17

Keywords

  • Computational geometry
  • Dynamic data structures
  • Range searching

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Dynamic orthogonal range searching on the RAM, Revisited'. Together they form a unique fingerprint.

Cite this