Does an efficient algorithm exist to determine the points of intersection between the edges of two possibly non-convex polygons?

Question

Here's the task I'm trying to solve:
Given a polygon A with N vertices and a polygon B with M vertices, find all intersections between a segment in A and a segment in B.
Both A and B may be non-convex.

So far, I have implemented the obvious solution(check every edge in A with every edge in B, O(M*N)).
Now, for certain polygons it is in fact possible that there are (almost) M*N intersections, so the worst case for any such algorithm is O(M*N).

My question is:
Does there exist an algorithm for determining the points of intersection between two non-convex polygons with complexity in the average case that is lower than O(N*M)

If yes, then please give me the name of the algorithm, if no - some resource that proves it to be impossible.

Answer 1

Excerpt from a paper on the Greiner-Hormann (PDF) polygon clipping algorithm:

... if we have a polygon with n edges and another with m edges, the number of intersections can be nm in the worst case. So the average number of intersections grows on the order of O(nm).

There is a well-known result in computational geometry based on the plane sweep algorithm, which says that if there are N line segments generating k intersections, then these intersections can be reported in time O((N+k) log(N)) [7]. Note that this relation yields an even worse complexity in the worst case.

I believe N in the second paragraph is m + n from the first paragraph. The average time depends the average value of k, the number of intersections. If there are only a handful of intersections the time goes to O(N log N).

The reference to the "well-known" result is:

[7] F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer, New York, 1985.

Here's a paper on the line sweep algorithm.