two convex polygon in a plane intersection

Question

find the intersection of two convex polygon among set of m polygons in a plane having all total n vertices in O(nlogm) time

Answer 1

Here is an O(n * log m) solution:

1. Let's check if any two polygons really intersect(not when one is
   contained within another). In this case, we can use standard algorithm
   to check if there is pair of intersecting segments in an arbitrary set
   of segments. There is a well-known O(n * log n) sweep line based solution
   for this problem(I will later show how to make it O(n * log m) for this
   particular problem). The set of segments we are interested in is just a set
   of all edges of given polygons. If an intersection is found, we are done.

2. Otherwise, we have to check if one polygon is contained within another. We
   will use sweep line again. The events should be sorted by their x-coordinate.
   There are 2 types of events: an edge of a polygon has started and an edge has
   ended. Let's iterate over all events and maintain a sorted set
   (using a balanced binary search tree) (edges should be compared by their
   y-coordinate, their relative order never changes because none of them intersect)
   of all started but not ended edges(the first type event adds one edge to
   the set, the second type removes one). I claim that one polygon is contained
   within another if and only if at some point there is a following sequence in
   the set: A B B A, where A are edges of one polygon and B are edges of
   the other. To check if this situation ever happens, it is sufficient to look at adjacent to the newly inserted/newly deleted element of the set after each insertion/deletion.
   So far, it looks like O(n * log n).

3. Now let's actually achieve O(n * log m) time complexity. Iterating over events in both 1. and 2. and maintaining the set is already O(n * log m) becuase there are at most O(m) elements in the set at a time(no more then two edges from each polygon). So the only remaining part is sorting all edges by x-coordinate. The idea here is pretty simple: for a convex polygon, it is possible to generate a sorted list of its edges in O(k) time, where k is the number of vertices(we can traverse it from the left to right in 2 directions and obtain two sorted lists that can be merged in linear time). So now we have m sorted lists with no more than n elements in total. Merging them into one sorted list in O(n * log m) time using a heap is a standard problem, too. That's it.