Exclusive disjunction of rectilinear polygons

76 Views Asked by At

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):enter image description here. 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.

1

There are 1 best solutions below

0
On BEST ANSWER

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: enter image description here

It is 2 "hair combs" with n and m teeth , and the one is rotated by 90 degrees.