# Two convex polygon intersection from set of m convex polygons with total n vertices

I have a set of m convex polygons $(p_1,p_2, \ldots p_m)$. $n_i$ is the number of vertices in $p_i$. $\sum_{i=1}^{m} n_i = n$. Each polygon has vertices listed in anti-clockwise direction, starting with the left most vertex (smallest x coordinate) in $p_i$. I have to present an $O(n \log m)$ algorithm that determines whether any two convex polygons of the set intersect.

How can I make the algorithm $n\log m$? As far as I know,two convex polygons $P_i$ and $P_j$ are said to intersect if they contain any point in common (that is, either their boundaries intersect or one polygon is contained within the other). Please help me.

• How is your data presented? – Zeno Nov 29 '14 at 5:50
• Data presented is given in the question itself. m convex polygons p1,p2,...pm are in plane. – user3621835 Nov 29 '14 at 5:54
• Does each polygon have an associated collection of $(x,y)$ coordinates that define that polygon? – Zeno Nov 29 '14 at 5:55
• I didn't understand what you are trying to tell. I found this question in a book. I am not able to solve this. – user3621835 Nov 29 '14 at 5:57
• I think each polygon has associated collection of (x,y) coordinates – user3621835 Nov 29 '14 at 5:59