Optimal color range reporting in one dimension

DOI10.1007/978-3-642-40450-4_63MaRDI QIDQ2849362zbMATH OpenOpenAlexFDO

Authors Yakov Nekrich, Jeffrey Scott Vitter

Publication date 17 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5029

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Color (or categorical) range reporting is a variant of the orthogonal range reporting problem in which every point in the input is assigned a emph{color}. While the answer to an orthogonal point reporting query contains all points in the query range $Q$, the answer to a color reporting query contains only distinct colors of points in $Q$. In this paper we describe an O(N)-space data structure that answers one-dimensional color reporting queries in optimal $O(k+1)$ time, where $k$ is the number of colors in the answer and $N$ is the number of points in the data structure. Our result can be also dynamized and extended to the external memory model.

Recommendations

• Colored Range Searching in Linear Space
• Near-optimal range reporting structures for categorical data
• Succinct color searching in one dimension
• Efficient range searching for categorical and plain data
• Optimal static range reporting in one dimension

Cited in

(6)

• I/O-optimal categorical 3-sided skyline queries
• Categorical range reporting with frequencies
• Succinct color searching in one dimension
• Optimal static range reporting in one dimension
• Near-optimal range reporting structures for categorical data
• I/O-efficient data structures for colored range and prefix reporting

This page was built for publication: Optimal color range reporting in one dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849362)