Efficient Data Structure for Closest Euclidean Distance The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&amp;Itemid=99999999&amp;category=18&amp;page=show_problem&amp;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?).
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.