Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time
If you have a voronoi diagram you have neighbour information of each $p$. You can use that to path search (using A* or even greedy depth first) to the 3 points that surround $q$. Then you can extract the closest from that.

If the voronoi is stored as a binary tree where each line divides the space into half-planes then it's just a dive into the search tree.