Polygons all of whose edges meet at right angles are called rectilinear polygons. Furthermore, lets assume integer coordinates at each point. The question is: Can we give an upper bound about the number of the area components created? An area component is a rectilinear polygon whose area belongs exclusively in the one of the two polygons (red areas):. For simplicity we can assume each polygon to be non self intersecting (wikipedia figure 1, bottom right excluded), but I would prefer to answer the general question. My feeling is that it should be the max of the two numbers of edges. Any insight/tip is welcome.
After asking an expect, this question seem to be common knowledge for people in the comp. geometry field. The bound is quadratic at worst(for n and m edges of the 2 polygons we can have O(n*m) segments, and there is a construction that makes the bound tight) and the example follows:
It is 2 "hair combs" with n and m teeth , and the one is rotated by 90 degrees.