In traditional colored range-searching problems, one wants to store a set of n objects with m distinct colors for the following queries: report all colors such that there is at least one object of that color intersecting the query range. Such an object, however, could be an ‘outlier’ in its color class. Therefore we consider a variant of this problem where one has to report only those colors such that at least a fraction t of the objects of that color intersects the query range, for some parameter t. Our main results are on an approximate version of this problem, where we are also allowed to report those colors for which a fraction (1 - e)t intersects the query range, for some fixed e> 0. We present efficient data structures for such queries with orthogonal query ranges in sets of colored points, and for point stabbing queries in sets of colored rectangles.
|Titel||Algorithms and Data Structures (Proceedings 8th International Workshop, WADS 2003, Ottawa, Canada, July 30-August 1, 2003)|
|Redacteuren||F.K.H.A. Dehne, F.R. Sack, M.H.M. Smid|
|Plaats van productie||Berlin|
|ISBN van geprinte versie||3-540-40545-3|
|Status||Gepubliceerd - 2003|
|Naam||Lecture Notes in Computer Science|
|ISSN van geprinte versie||0302-9743|