Can someone help with a following problem: report all intersections between two simple polygons in O(n+k) where n - is a total number of polygon edges and k - is number of intersections. As a result - algorithm should output pairwise edges that interesect. It is very important that algorithm should be linear.
I've read that this can be solved in given time with linking to U. Finke and K. Hinrichs. Overlaying simply connected planar subdivisions in linear time. But I couldn't find this paper and I'm not even sure that this is my case.
