Problem: Supoose we want to divide $\mathbb{R^2}$ into $N$ regions separated by straight lines. What is the maximum number of boundary lines we could have? I also pose the restriction that between any two regions, there can be only one boundary line (so zigzagging a boundary does not increase the count). For example, here I attempt to find the maximum number of boundaries for $N = 4$ regions in $\mathbb{R}^2$, and I count 6 boundary lines. enter image description here But is there a general formula for general integer $N$? Can someone point me to a reference on this problem?

  • 2
    $\begingroup$ When you say "straight lines", do you mean infinite lines, rays and segments? Can those lines intersect? $\endgroup$ – ajotatxe Sep 4 '18 at 18:32
  • $\begingroup$ These lines cannot intersect (except at the vertices of course). They can be segments, rays (these two are shown in my example) and infinite lines (sure, we can split $\mathbb{R}^2$ in half). I just thought this seems to be an interesting problem, so please excuse my problem statement not being fully rigorous... $\endgroup$ – Longti Sep 4 '18 at 18:42
  • $\begingroup$ See en.wikipedia.org/wiki/Planar_graph#Other_planarity_criteria $\endgroup$ – lhf Sep 5 '18 at 0:15
  • $\begingroup$ @lhf It seems that I can bound the number of edges $e$ with the number of vertices $v$, but unless I pose more restriction on the faces, I can't seem to find a bound of $e$ by the number of faces $\endgroup$ – Longti Sep 5 '18 at 1:23

Your Answer

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

Browse other questions tagged or ask your own question.