It would be interesting to see the performance characteristics between
1) building a Voronoi tessellation from the given points
2) at each mouse movement perform point-in-polygon queries on all polygons until found
3) rebuild Voronoi as data changes
or
1) at each mouse movement calculate distance-to-point for each point
2) select the shortest
Not sure if I'm misreading your step 2 description for the first strategy, but one of the great things about using this type of mouseover region is that each polygon is already tied to a single point - so there's no need to do any query for contained points on mouseover. The lookup time for contained points is constant.
How do go from cursor coordinates to a polygon? Once you've done that, finding the the associated point in the scatter plot should be constant, but mapping from cursor to polygons in faster than linear time seems non-trivial.
k-d trees sound closer to what you'd want to do cursor coordinates to scatter plot point lookups.
