Is the intersection test for a convex polygon less than O (n)?

Question

I have 2 convex polygons (2d) and I would like to check if 2 polygons intersect. In fact, I will repeatedly move and rotate the polygons, so I can also do some preliminary calculations to get a quick answer to this problem.

I am looking for an algorithm with low complexity.

I know that you can verify that the point lies in a convex polygon in O (log (n)), and I was wondering if I could do some dichotomy around the points of another polygon to get the result. If there are existing algorithms / documents on this topic?

Answer 1

The Gilbert-Johnson-Keerthi (GJK) algorithm is what you are looking for. This is surprisingly easy to implement and detects a collision in O (log (n)).