Minimum distance between convex Hull: Naive approach

Question

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?

Answer 1

No !

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$.