1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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 produced

  1. Mar 7, 2017 #1
    1. The problem statement, all variables and given/known data
    Suppose n straight lines are drawn on a plane. When these lines are removed, the plane falls apart into several connected components called regions.A region R is is said to be convex if it has the following property: whenever two points are in R, then the entire line segment joining them is in R.Suppose no two of the n lines are parallel. Which of the following is true?
    A) O(n) regions are produced, and each region is convex.
    B) O(n2) regions are produced but they need not all be convex.
    C) O(n2) regions are produced, and each region is convex.
    D) O(nlogn) regions are produced, but they need not all be convex.
    E) All regions are convex but there may be exponentially many of them.
    2. Relevant equations


    3. The attempt at a solution

    Someone please explain what we have to start with , i.e what is there in the plane before those straight lines ?

     
  2. jcsd
  3. Mar 7, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    There is nothing in the plane.

    Here is an example of the plane with two lines (imagine the lines being extended to infinity)

    straight_line_example.png

    How many different regions do you find?
     
  4. Mar 7, 2017 #3
    I find 4 regions. Sir, but it is mentioned that the regions are formed after removing the lines. This is what confuses me. and the region have "connected components" what is there to connect if the lines are gone ?
     
  5. Mar 7, 2017 #4

    Mark44

    Staff: Mentor

    I don't understand this either. I read the first part, "When these lines are removed," to mean that the lines are like cutting a piece of paper with a pair of scissors. If the cuts are parallel, the paper is divided into three pieces. If the cuts are not parallel, you get four pieces. (I'm assuming that paper is large enough to include the point of intersection of the two lines/cuts.)

    The part about the parts being "connected components" is unclear. I believe what the write is trying to convey is that each piece is connected to itself, with no region consisting of two unconnected parts. I don't see how any piece could be connected to any other.
     
  6. Mar 7, 2017 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The set of all points of the plane minus the points of the lines has different regions - four in the example above.
    "Connected" refers to the points within such a region, not between regions.

    The phrasing is a bit odd.
     
  7. Mar 8, 2017 #6
    region.png

    Since the lines need not be of finite length, above figure is possible. there are 7 lines and 2 regions here. But the inner region is not convex as per the red points.
    So this proves there can be non convex regions


    Or is it that "line" means infinite length and "line segment" means finite ?
    In that case i don't think there any way to have non convex regions


    Now the question is to find the max number of regions that can be formed with n lines(with no two lines parallel).
    Can you give a start ?
    I have some ideas like , at the max a new line is going to multiply the number of regions by two , (but i don't see this happening except for n=2)
    and if all lines are intersected at a point, then number of regions will be twice the number of lines.

    But i cant move any further :(
     
  8. Mar 8, 2017 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If you assume no that you never have more than two lines intersecting at any given point you should be able to find a simple pattern describing the number of regions. Think about what happens when you add one more line to an existing set of regions.
     
  9. Mar 8, 2017 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I'm quite sure the lines do not have end, otherwise the problem is ill-defined.
    That won't happen in general, but the possibility of that doesn't change the answer.
     
  10. Mar 8, 2017 #9
    OK, let's see. No lines, one region. One line, two regions. Two lines, four regions. Three lines, seven regions (unless they all pass hrough the same point, giving one "region" of zero area). Now if you have n infinite non-parallel lines, the n+1th line will cross each of these lines (passing from one region to another) once, i.e. it passes through n+1 regions, dividing each in two. Therefore the number of regions N(n+1) = N(n) + n+1. Looking at the first few values we see that N(n) = n(n+1)/2 + 1. Thus N(n) is O(n2) (I think; I have just looked up Big O Notation, never having heard of it before). It seems to me they must all be convex, but I don't know that I could prove it. I suppose if you had a concave region as in the diagram above, those two lines must extend beyond their point of meeting to intersect other lines, and that "region" would be divided into multiple convex regions.
     
  11. Mar 8, 2017 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Right.

    For a more formal proof that the regions have to be convex: Assume they are not. Then there are two points A,B in a region where some point between them has to be a border of the region, i. e. part one of the n lines. You can show that this implies that A and B cannot be in the same region.
     
  12. Mar 8, 2017 #11
    Ya. Because the Big O notation considers the worst case scenario. Right ?

    Awesome! . Now i got it. Thanks. :)

    border of the region which is a line is boundless and that prevents A and B to be in the same region. Right ?
    Thanks a lot Sir :)
    I think i got it now :)
     
  13. Mar 8, 2017 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Right.
    Right.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted