 <p>I'm thinking all you are really looking for is where <a href="http://en.wikipedia.org/wiki/Line_segment_intersection" rel="nofollow">line segment intersections</a>. This can be done in O((N+k) log N), where N is the number of line segments (roughly the number of vertices) and k is the number of intersections. Using the Bentley-Ottmann algorithm. This would probably be best done using ALL of the polygons, instead of simply considering only two at a time. </p> <p>The trouble is keeping track of which line segments belong to which polygon. There is also the matter that considering all line segments may be worst than simply considering only two polygons, in which case you stop as soon as you get one valid intersection (some intersections may not meet your requirements to be count as an overlap). This method is probably faster, although it may require that you try different combinations of polygons. In which case, it's probably better to simply consider all line segments.</p>