Colored Range Searching in Linear Space

Roberto Grossi, Søren Juhl Vind

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

In colored range searching, we are given a set of n colored points in d ≥ 2 dimensions to store, and want to support orthogonal range queries taking colors into account. In the colored range counting problem, a query must report the number of distinct colors found in the query range, while an answer to the colored range reporting problem must report the distinct colors in the query range. We give the first linear space data structure for both problems in two dimensions (d = 2) with o(n) worst case query time. We also give the first data structure obtaining almost-linear space usage and o(n) worst case query time for points in d > 2 dimensions. Finally, we present the first dynamic solution to both counting and reporting with o(n) query time for d ≥ 2 and d ≥ 3 dimensions, respectively.
Original languageEnglish
Title of host publicationAlgorithm Theory – SWAT 2014 : Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory
EditorsR. Ravi, Inge Li Gørtz
PublisherSpringer
Publication date2014
Pages229-240
ISBN (Print)978-3-319-08403-9
ISBN (Electronic)978-3-319-08404-6
DOIs
Publication statusPublished - 2014
Event14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014) - Copenhagen, Denmark
Duration: 2 Jul 20144 Jul 2014
Conference number: 14
http://algolog.compute.dtu.dk/swat2014/

Conference

Conference14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014)
Number14
CountryDenmark
CityCopenhagen
Period02/07/201404/07/2014
Internet address
SeriesLecture Notes in Computer Science
Volume8503
ISSN0302-9743

Cite this

Grossi, R., & Vind, S. J. (2014). Colored Range Searching in Linear Space. In R. Ravi, & I. L. Gørtz (Eds.), Algorithm Theory – SWAT 2014: Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory (pp. 229-240). Springer. Lecture Notes in Computer Science, Vol.. 8503 https://doi.org/10.1007/978-3-319-08404-6_20