1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gandalf61 Sep 3 '18 at 16:06
  • $\begingroup$ Can you make your argument a bit more concrete? Like a proof sketch? Intuition-wise I think you are right though $\endgroup$ – Paramar Sep 3 '18 at 17:39
  • $\begingroup$ 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. $\endgroup$ – gandalf61 Sep 4 '18 at 9:09
  • $\begingroup$ 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 $\endgroup$ – Paramar Sep 4 '18 at 9:57
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.