Abstract
Given n horizontal segments, each associated with a color from [σ], the Categorical Segment Stabbing problem is to find the distinct K colors stabbed by a vertical line. When the end-points of the segments are distinct and lie in [1, 2n], we present an (2 + ϵ)n log σ + O(n)-bit index with O(K/ϵ) query time, where ϵ(0, 1].When the end-points are arbitrary real numbers, a standard reduction to the above scenario improves the existing bounds of Janardan and Lopez. We also present results for few other variations: • reporting the top-k colors that are stabbed, where each color has a fixed priority. • handling these scenarios when the given segments form a tree range.