# Finding minimum distance between two convex polygon

We have two disjoint convex polygon $$P,Q$$, each with size $$n$$ , how we can find minimum distance between two convex polygon $$O(\log n)$$?

We think for each points in $$P,Q$$ we must check to find minimum distance that time complexity is $$O(n^2)$$.

• Are you sure it’s $O(\log n)$? You can achieve $O(\log^2 n)$ with ternary search.
– user114966
Mar 25 at 23:46
• Just finding the minimum distance between vertex points is not enough, consider this scenario: i.imgur.com/aFihJeP.png.
– orlp
Mar 26 at 0:09
• Please see: pub.ist.ac.at/~edels/Papers/… Mar 26 at 2:44