Find collision between 2 polygons

Question

It's problem from the book:

"Computational Geometry: Algorithms and Applications", Springer-Verlag.

Given two simple and disjoint polygons P and Q, where P lies strictly to the left of Q, computes the first points on the polygons that will collide if P is translated horizontally and in the positive x-direction, or determines that they do not collide.

I have a quadratic solution, but it should be O((n+m) log(n+m))

Answer 1

Sort both polygons top to bottom and implement a sweepline process. The vertices are the event points. While sweeping, keep a trace of the rightmost edge of P and the leftmost edge of Q. You can draw horizontal segments in between, and keep the shortest of all.