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

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

Your Answer

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

Browse other questions tagged or ask your own question.