See Amato, Nancy M (1994) for details of the difference between separation (sigma: σ) and closest visible vertex (CVV).
Refer to P
and Q
as the two polygons with n
and m
vertices, respectively.
For the purposes of this discussion, a key insight is that it is enough to find the closest edge to each vertex in order to compute the minimum separation between P
and Q
.
This means iterating over all vertices, and finding a nearest neighbour. Thus, a time complexity in O((m + n) * log(m * n))
should be expected.