# Exclusive disjunction of rectilinear polygons

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.

• Since each "area component" in your examples has either two vertices from one polygon or one vertex from each polygon, my guess would be the maximum number of area components is half the total number of vertices in the two polygons. – gandalf61 Sep 3 '18 at 16:06
• Can you make your argument a bit more concrete? Like a proof sketch? Intuition-wise I think you are right though – Paramar Sep 3 '18 at 17:39
• I've had second thoughts - I think I have found a counterexample to my hypothesis ! If you consider an L-shaped polygon (6 vertices) and a rectangle, I think the maximum number of area components is 4, not 5. So "half the total number of vertices" is not correct after all. – gandalf61 Sep 4 '18 at 9:09
• yes it is 4, but you meant, up to half. Am I right? After all, I am asking for the upper bound. The exact number varies a lot, as the area components are not necessarily square. In any case, if you have a suggestion for a full proof, do not hesitate – Paramar Sep 4 '18 at 9:57