What is the fastest algorithm to calculate the minimum distance between two sets of points?

Perhaps you should check out (PDF warning! Also note that, for some reason, the order of the pages is reversed) “Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets” by Toussaint and Bhattacharya:

It is shown in this paper that the
minimum distance between two finite
planar sets if [sic] n points can be
computed in O(n log n) worst-case
running time and that this is optimal
to within a constant factor.
Furthermore, when the sets form a
convex polygon this complexity can be
reduced to O(n).

If the two polygons are crossing convex ones, perhaps you should also check out (PDF warning! Again, the order of the pages is reversed) “An Optimal Algorithm for Computing the Minimum Vertex Distance Between Two Crossing Convex Polygons” by Toussaint:

Let P = {p₁,
p₂,…, p_m} and Q = {q₁, q₂,…,
q_n} be two intersecting polygons whose vertices are specified
by their cartesian coordinates in
order. An optimal O(m + n)
algorithm is presented for computing
the minimum euclidean distance between
a vertex p_i in P and a
vertex q_j in Q.