Paper Info
Title
Counting colors in boxes
Abstract
Let P be a set of n points in Rd, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the form: Given an axis-parallel box Q, count the number of distinct colors of the points of P ∩ Q. We present a general and relatively simple solution that has polylogarithmic query time and worst-case storage about O(nd). It is based on several interesting structural properties of the problem that we derive. We also show that for random inputs, the data structure requires almost linear expected storage. We then present several techniques for achieving space-time tradeoff. In R2, the most effi- cient solution uses fast matrix multiplication in the preprocessing stage. In higher dimensions we use simpler tradeoff mechanisms, which behave just as well. We give a reduction from ma- trix multiplication to the offline version of problem, which shows that in R2 our time-space tradeoffs are close to optimal in the sense that improving them substantially would improve the best exponent of matrix multiplication. Finally, we present a generalized matrix multiplication problem and show its intimate relation to counting colors in boxes in any dimension.
Year
DOI
Venue
2007
10.1145/1283383.1283467
Symposium on Discrete Algorithms
Keywords
Field
DocType
efficient solution,preprocessing p,matrix multiplication,space-time tradeoff,present algorithm,simple solution,linear expected storage,generalized matrix multiplication problem,data structure,preprocessing stage,space time
Discrete mathematics,Data structure,Combinatorics,Colored,Multicast scheduling,Exponent,Of the form,Preprocessor,Matrix multiplication,Mathematics
Conference
ISBN
Citations 
PageRank 
978-0-89871-624-5
14
0.92
References 
Authors
21
4
Name
Order
Citations
PageRank
Haim Kaplan13581263.96
Natan Rubin29211.03
Micha Sharir384051183.84
Elad Verbin433620.78