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

The paper presents an algorithm to solve the following problem: given a set of \(n\) points arbitrarily distributed in the plane, find \(k\) nearest neighbors of a query line segment. First, an improved searching technique is developed for reporting the number of points that lie inside a query triangle. This counting query problem is solved in \(O(\log n)\) time with \(O(n^2)\) preprocessing time and space. Then the new triangular range searching technique leads to the solution of the \(k\)-nearest neighbors query in \(O(\log^2 n + k)\) time.