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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.