License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.35
URN: urn:nbn:de:0030-drops-135742
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13574/
Go to the corresponding LIPIcs Volume Portal

Lau, Joshua ; Ritossa, Angus

Algorithms and Hardness for Multidimensional Range Updates and Queries

pdf-format:
LIPIcs-ITCS-2021-35.pdf (0.6 MB)

Abstract

Traditional orthogonal range problems allow queries over a static set of points, each with some value. Dynamic variants allow points to be added or removed, one at a time. To support more powerful updates, we introduce the Grid Range class of data structure problems over arbitrarily large integer arrays in one or more dimensions. These problems allow range updates (such as filling all points in a range with a constant) and queries (such as finding the sum or maximum of values in a range). In this work, we consider these operations along with updates that replace each point in a range with the minimum, maximum, or sum of its existing value, and a constant. In one dimension, it is known that segment trees can be leveraged to facilitate any n of these operations in Õ(n) time overall. Other than a few specific cases, until now, higher dimensional variants have been largely unexplored.
Despite their tightly-knit complexity in one dimension, we show that variants induced by subsets of these operations exhibit polynomial separation in two dimensions. In particular, no truly subquadratic time algorithm can support certain pairs of these updates simultaneously without falsifying several popular conjectures. On the positive side, we show that truly subquadratic algorithms can be obtained for variants induced by other subsets.
We provide two general approaches to designing such algorithms that can be generalised to online and higher dimensional settings. First, we give almost-tight Õ(n^{3/2}) time algorithms for single-update variants where the update and query operations meet a set of natural conditions. Second, for other variants, we provide a general framework for reducing to instances with a special geometry. Using this, we show that O(m^{3/2-ε}) time algorithms for counting paths and walks of length 2 and 3 between vertex pairs in sparse graphs imply truly subquadratic data structures for certain variants; to this end, we give an Õ(m^{(4ω-1)/(2ω+1)}) = O(m^1.478) time algorithm for counting simple 3-paths between vertex pairs.

BibTeX - Entry

@InProceedings{lau_et_al:LIPIcs.ITCS.2021.35,
  author =	{Joshua Lau and Angus Ritossa},
  title =	{{Algorithms and Hardness for Multidimensional Range Updates and Queries}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13574},
  URN =		{urn:nbn:de:0030-drops-135742},
  doi =		{10.4230/LIPIcs.ITCS.2021.35},
  annote =	{Keywords: Orthogonal range, Range updates, Online and Dynamic Data Structures, Fine-grained complexity, Cycle counting}
}

Keywords: Orthogonal range, Range updates, Online and Dynamic Data Structures, Fine-grained complexity, Cycle counting
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

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