Finding the Voronoi cell a point belongs to
I will consider this problem on a Voronoi diagram with $n$ sites and $m$ query points. 
Generally, trapezoidal decompositions work nicely for point-location. However, as we here have a subdivision of convex cells, we instead can construct a triangulation of the Voronoi diagram in $O(n)$ that can answer point location queries in $O(\log n)$, which is in fact optimal$^*$. (The complexity for the triangulation is in terms of the edges, but this doesn't matter as the number of edges of a Voronoi diagram is it most $3n-6$). 

So, if we are given a Voronoi diagram on $n$ sites and $m$ query points at once, this gives an $O(n+m\log n)$ time algorithm. It makes no difference when we get the query points, so this algorithm is also online in that sense. 

It isn't very clear what would be provided if the sites would be 'online', as some edges will be removed and others added when adding sites. If the number of edges added and removed are given, there is a constant number of them and the triangulation can be updated in constant time, so the total running time would remain $O(n+m\log n)$.

Another approach that may not be as good in theory but might work better in practice is to use quadtrees: you can store the set of closest sites for every square in the tree and partition the squares until the size of all those sets is small enough. Then simply locate the square containing the query point and compare all sites in the set for that square to find the nearest site.



*: See the paper: Kirkpatrick, David. "Optimal search in planar subdivisions." SIAM Journal on Computing 12.1 (1983): 28-35.