Chromatic distribution of k-nearest neighbors of a line segment in a planar colored point set

Let P be a set of n colored points distributed arbitrarily in R2. The chromatic distribution of the k-nearest neighbors of a query line segment ℓ is to report the number of points of each color among the k-nearest points of the query line segment. While solving this problem, we have encountered another interesting problem, namely the semicircular range counting query. Here a set of n points is given. The objective is to report the number of points inside a given semicircular range. We propose a simple algorithm for this problem with preprocessing time and space complexity O(n3), and the query time complexity O(logn). Finally, we propose the algorithm for reporting the chromatic distribution of k nearest neighbors of a query line segment. Using our proposed technique for semicircular range counting query, it runs in O(log2n) time.