Checking convex polygon intersection in less than O(n)?

Question

I have 2 convex polygons (2d) and I would like to check if the 2 polygons intersect. In fact, I will move and rotate the polygons many times, so I can also do some precomputations to obtain a fast answer to this problem.

I am looking for a low complexity algorithm.

I know that it is possible to check that a point lie in a convex polygon in O(log(n)), and I was wondering if I can do some kind of dichotomy around the points of the other polygon to obtain the result. If there any existing algorithms / papers on this topic ?

Yes, it's possible in O(log(n)): cs.princeton.edu/~chazelle/pubs/… — Niklas B.
What are the typical values of n ? A first approach is by a tight bounding circle. Axis-parallel bounding box (then rotated) is another option. — Yves Daoust
n can be something about 500 points. Yes, i will do some first tests to exclude fast. — Renaud

Ivaylo Strandjev Ivaylo Strandjev · Accepted Answer · 2016-02-09T16:24:02

The Gilbert–Johnson–Keerthi(GJK) algorithm is just what you are looking for. It is surprisingly easy to implement and it detects collision in O(log(n)).

Checking convex polygon intersection in less than O(n)?

1 Answers