Minimum distance between a set of points and a specific point

I would probably recommend using a dynamic convex hull algorithm or something like it. The furthest point in this case is always on the convex hull. Add the point you are tracking to the hull (O(log N)), since you know one point on the hull, in theory you might be able to find the furthest point in O(log h) but at worst it would be O(h) where h is the number of points on the convex hull. In a random point set, h is roughly O(sqrt N), but depends on what your point set looks like.