In order to compute minimum distance between convex hulls, can we just use a naive approach like measuring all the points from first convex hull to second convex hull? And take the minimum value?
The hulls are convex polygons, and the closest distance between two convex polygons can occur between two vertices or between a vertex and an edge. (Not counting the overlapping polygons.)
If the hulls have many sides, the total work is proportional to $NM$. You can do a little better as follows:
Try all edges of the polygon that has the less sides, say $N$. For a given edge, the distance of the vertices of the other polygon to the line of support is a function with a single minimum. The minimum can be detected as the vertex of the other polygon that joins a "nearing" edge and a "moving away" edge.
By a process similar to a dichotomic search, this vertex can be detected in $\log_2M$ operations, giving a total workload proportional to $N\log_2M$.