Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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.

share|improve this question

closed as off topic by whuber Jul 3 '12 at 19:22

Questions on Geographic Information Systems Stack Exchange are expected to relate to geographic information systems within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Cross-posted at scicomp.stackexchange.com/questions/2041. –  whuber Jul 3 '12 at 19:22
add comment