Suppose that you are given m convex polygons P1; P2; : : : ; Pm in the plane. Let ni denote the
number of vertices on Pi and n =
Pm
i=1 ni. The vertices of each polygon is listed in counter-
clockwise order, starting at the leftmost vertex of Pi (that is, the one with the smallest x-
coordinate). Two polygons Pi and Pj are said to intersect if they contain any point in common
(that is, either theirboundaries intersect or one polygon is contained within the other). Present
an O(n logm) algorithm that determines whether any two polygons of the set intersect

## Intersection of two convex polygons

number of vertices on Pi and n =

Pm

i=1 ni. The vertices of each polygon is listed in counter-

clockwise order, starting at the leftmost vertex of Pi (that is, the one with the smallest x-

coordinate). Two polygons Pi and Pj are said to intersect if they contain any point in common

(that is, either theirboundaries intersect or one polygon is contained within the other). Present

an O(n logm) algorithm that determines whether any two polygons of the set intersect

This Question is not yet answered!

## Related Answered Questions

## Related Open Questions