2013/06/21 by Yakov Nekrich, Nekrich, Yakov, Jeffrey Scott Vitter +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1306.5029
arxiv created 2013/06/21 · arxiv updated 2013/06/24
Color (or categorical) range reporting is a variant of the orthogonal range reporting problem in which every point in the input is assigned a 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.