# Minimum distance between convex Hull: Naive approach

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?

• Are they disjoint? If not, the minimal distance between two points is zero. If yes, how to understand the distance? As the minimum of distances between two points, or in the Hausdorff sense? – szw1710 Jul 9 '18 at 22:15

## 1 Answer

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