How to get all intersections between two simple polygons in O(n+k?

How to get all intersections between two simple polygons in O(n+k)

• Basically the formulation of the problem I'd like to solve is very simple. Given 2 simple polygons (without self-intersections) report all intersecting edge pairs in O(n+k) time, where n - is a total number of edges, k - number of intersections between two polygons. It is very important to stay within mentioned time hardness. What does surprise me, that I could hardly find information on this subject. Polygon intersections seems to be so natural and important problem. Anyway at the moment I don't have a clue if it is even possible to do it in O(n+k). Can please someone help with lower bounds for this problem? Some additional points on my question: Polygon clipping with set operations and intersection reporting (about which my question was) seems to be slightly different problems - Having found intersecting edges you would have to constract a polygon which is a result of clipping/set operation. An approach based on segment intersection algorithm won't work for me. As it is proved that worst case takes O(nlogn+k). I'm not insisting that an algorithm with such hardness exist - it may not. But in this case I would really appreciate if someone could provide a lower bound proof for my problem - tons of papers provide some very interesting algorithm (usually with O(nlogn+k) complexity) but for some reason don't mention the lower bound.

• Answer:

  The $\mathcal{O}(n+k)$ algorithms seem to be limited to convex polygons. The fastest algorithms that I have found http://www.sciencedirect.com/science/article/pii/S0098300499000710 and have approximately $\mathcal{O}(n\log(n))$ algorithms. According to http://www.tcs.tifr.res.in/~ghosh/lec-coimbatore-jan2011.pdf, the problem of simple polygon intersection is linear time transformable to line-segment intersection testing, which has an optimal bound of approximately $\mathcal{O}(n\log(n) + k)$ according to http://dl.acm.org/citation.cfm?id=147511 article.