0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – szw1710 Jul 9 '18 at 22:15
0
$\begingroup$

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

enter image description here


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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.