A sweep line algorithm for nearest neighbour queries.
J. Dinis, Margarida Mamede · 2002
We introduce a novel algorithm for solving the nearest neighbour problem when the query points are known in advance, which is based on Fortune's plane sweep algorithm. The crucial idea is to use the wavefront for solving the nearest neighbour queries as the Voronoi diagram is being computed, instead of storing it in an auxiliary data structure, as the algorithm presented by Lee and Yang [9] does, and then querying that data structure. Although