Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment

We present an efficient algorithm for finding k nearest neighbors of a query line segment among a set of points distributed arbitrarily on a two dimensional plane. Along the way to finding this algorithm, we have obtained an improved triangular range searching technique in 2D. Given a set of n points, we preprocess them to create a data structure using O(n²) time and space, such that given a triangular query region Δ, the number of points inside Δ can be reported in O(logn) time. Finally, this triangular range counting technique is used for finding k nearest neighbors of a query straight line segment in O(log²n+k) time.