Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of Regions in a Plane

  1. Jun 6, 2004 #1
    Hi everyone,

    I'm stumped on this problem: Let [itex]R_n[/itex] denote the nubmer of regions into which the plane is divided by [itex]n[/itex] lines. Assume that each pair of lines meets in a point, but that no three lines meet in a point. Derive a recurrence relation for the sequence [itex]R_1[/itex], [itex]R_2[/itex], ....

    After doing a couple of examples, the recurrence relation seems to be
    [tex]R_n = R_{n-1} + n[/tex]​
    . I want to prove that this is the proper recurrence relation. More specifically, I want to show that when I cut a plane consisting of [itex]R_k[/itex] regions with the appropriate line, [itex]k+1[/itex] of those regions will be divided in two so that the number of regions is [itex]R_{k+1} = R_k + k + 1[/itex]. I can't think of any geometrical argument for this. Any tips?
     
    Last edited: Jun 6, 2004
  2. jcsd
  3. Jun 6, 2004 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Okay, well you know there are k existing lines. Now, the (k+1)th line can, at maximum, cut through the k lines (if it is parallel to any one line, it will not cut it). Show that this is possible, and that it is optimal. Also, recognize that if it passes through n lines, it cuts n+1 regions in half. Basically, you can think of the existing lines forming boundaries of regions, and include some boundaries at infinity. If the line goes from one boundary at infinity to another at infinity, and cuts through n lines, then the points it intersects (imagine it intersects some points at the infinite boundary) form a set. You'll notice that every consecutive pair of points it intersects means that it cuts a region in half. If there are n points in the set (including the 2 at infinity) then there will be n-1 split regions. Of course, since there are k lines, and we're including 2 boundary points, n-1 = k+1, so it splits k+1 regions. This is of course a rough argument, you can fix it up so that you're not treating it as though there are lines at infinity, but the idea is right.
     
  4. Jun 7, 2004 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Or you can use the Euler relation for the plane (F(n)+V(n)-E(n)=1), along with AKG's observations, (but you don't have to worry about regions anymore) i.e:

    1. the (n+1)th line intersects the previous n lines creating n new vertices. Or, V(n+1)=V(n)+n

    2. These intersections give rise to n new edges on the existing n lines and n+1 edges on the (n+1)th line.
    Or E(n+1)=E(n)+n+1+n=E(n)+2n+1

    Now plug these into Euler to get
    F(n+1)=1-V(n+1)+E(n+1)=[1-V(n)+E(n)]+2n+1-n=F(n)+n+1

    which is what you want.
     
  5. Jun 7, 2004 #4
    My lack of intuition disables me from understanding your argument very well.

    What do you mean 'optimal'? What makes it optimal? The only way I can think of showing this is using one of Euclid's axioms.

    Interesting argument. Maybe things would be simpler if I just assume the plane is finite. I'll think about this some more and I'll post a proper argument when I have something.
    I would like to solve this problem without using graph theory (since this problem came from the chapter right before the chapters on graph theory). I'll consider this solution later on. Thanks.
     
  6. Jun 7, 2004 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is simply an extension of the Euclidean axiom that says "2 lines intersect at most, at one point". I don't believe there is any need to optimize anything in it.
     
  7. Jun 7, 2004 #6

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    I suppose it's a trivial point, but show that it is, for example, better than having 2 parallel lines in there somewhere, or having a line pass through an existing point of intersection. I had a nice big thing on proving this with diagrams and everything, including an extension to 3-space, as well as the recurrence relation derived for 3-space, but I think I only have it in hard copy now. meh...

    You can treat the plane (two-space) as an infinitely large square, or circle, whatever works best. The assignment I was talking about in the paragraph above asked about slicing a pizza and a loaf of bread, and we did this with some analogies, treating 2-space as a very big pizza...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number of Regions in a Plane
  1. The Number Plane (Replies: 8)

Loading...