Efficient Data Structure for Closest Euclidean Distance

Question

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628.

A network of autonomous, battery-powered, data acquisition stations has been installed to monitor the climate in the region of Amazon. An order-dispatch station can initiate transmission of instructions to the control stations so that they change their current parameters. To avoid overloading the battery, each station (including the order-dispatch station) can only transmit to two other stations. The destinataries of a station are the two closest stations. In case of draw, the first criterion is to chose the westernmost (leftmost on the map), and the second criterion is to chose the southernmost (lowest on the map). You are commissioned by Amazon State Government to write a program that decides if, given the localization of each station, messages can reach all stations.

The naive algorithm of course would build a graph with stations as vertices and calculate the edges from a given vertex by searching through all other vertices for the closest two. Then, we could simply run DFS/BFS. Of course, this takes $O(V^2)$ time to construct the graph (which does pass the test cases). My question, though, is if we can build the graph any faster with an appropriate data structure. Specifically, given an arbitrary query point $p$ and a given set of points $S$, can we organize the points in $S$ in such a way that we can quickly find the two closest points in $S$ to $p$ (say, in $\log V$ time?).

Answer 1

If I understand this correctly, most spatial indexes could be used.

Spatial indexes typically have about $O(log{V})$ insertion time and similar lookup time for nearest neighbors. Of course you can create a Voronoi diagram from that, but you can also use the index directly to find the closest neighbors whenever you need them.

For low dimensionality (2D, 3D), The common families of spatial indexes are kd-trees (quite simple and generally good, but tend to have problems with dense clusters of points), quadtrees (a bit harder to implement yourself because numerical precision can be tricky) and R-Tree (hardest to implement, but give best guaranteed performance, especially the R*Tree (R-Star-Tree)).

In case you are using C++, have a look at libSpatialIndex or the Boost R-Tree. If you are using Java, have a look at my TinSpIn library.

The technical term for this is "$k$ nearest neighbor queries" or "$k$-NN queries", with $k$ referring to the number of nearest neighbors you want to find.

Answer 2

It seems that the relevant data structure might be a dynamic Voronoi diagram.

Voronoi diagrams are often the answer when a set of points on the plane is involved.

In this case, since the point set is evolving, you want a dynamic version.