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.SoCG.2020.59
URN: urn:nbn:de:0030-drops-122170
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12217/
Go to the corresponding LIPIcs Volume Portal

Nekrich, Yakov

Four-Dimensional Dominance Range Reporting in Linear Space

pdf-format:
LIPIcs-SoCG-2020-59.pdf (0.5 MB)

Abstract

In this paper we study the four-dimensional dominance range reporting problem and present data structures with linear or almost-linear space usage. Our results can be also used to answer four-dimensional queries that are bounded on five sides. The first data structure presented in this paper uses linear space and answers queries in O(log^{1+ε} n + k log^ε n) time, where k is the number of reported points, n is the number of points in the data structure, and ε is an arbitrarily small positive constant. Our second data structure uses O(n log^ε n) space and answers queries in O(log n+k) time.
These are the first data structures for this problem that use linear (resp. O(n log^ε n)) space and answer queries in poly-logarithmic time. For comparison the fastest previously known linear-space or O(n log^ε n)-space data structure supports queries in O(n^ε + k) time (Bentley and Mauer, 1980). Our results can be generalized to d ≥ 4 dimensions. For example, we can answer d-dimensional dominance range reporting queries in O(log log n (log n/log log n)^{d-3} + k) time using O(n log^{d-4+ε} n) space. Compared to the fastest previously known result (Chan, 2013), our data structure reduces the space usage by O(log n) without increasing the query time.

BibTeX - Entry

@InProceedings{nekrich:LIPIcs:2020:12217,
  author =	{Yakov Nekrich},
  title =	{{Four-Dimensional Dominance Range Reporting in Linear Space}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{59:1--59:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12217},
  URN =		{urn:nbn:de:0030-drops-122170},
  doi =		{10.4230/LIPIcs.SoCG.2020.59},
  annote =	{Keywords: Range searching, geometric data structures, word RAM}
}

Keywords: Range searching, geometric data structures, word RAM
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

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