Circles, Lines and Regions

Last week when I was trying to sort out a combinatorial question related to my research, I accidentally ended up redoing some fun geometry of the type covered (?) in an undergraduate discrete math, or intro to topology course.

I’m going to ramble on a bit about some fun pictorial counting games, with no particular point in mind, except to show some pretty relations.

The first has to do with geometrical arrangements on a sphere.  It’s not hard to see (unless you are Camille Jordan) that if you draw a circle on a sphere it separates the surface into two regions.

A sphere divided by a great circle

A sphere divided

 

The circle on the sphere in the figure is a special kind of curve called a great circle, which divides the sphere into to equal halves.  A great thing about great circles is that any two of them intersect in exactly two points.  You can easily see this if we add another line to the picture.

two great circles on a sphere

Two great circles on a sphere make 4 regions

 

Notice that now the sphere has been split into four.   What happens if we add another great circle?  The diagram begins to get a little busy.

Three great circles separate a sphere into 8 regions

Three great circles separate a sphere into 8 regions

Now a new great circle has been added in green.   The red numbers should be “seen” as being on the front of the sphere, whereas the green italicized numbers should be seen as being written on the “inside” of the sphere (to label regions that are mostly on the back).

What we have now is just a somewhat skewed version of the well known fact that three planes with one common point divide space into octants (whereas two lines divide a plane into quadrants).

Notice that up until now, each time we’ve added a new great circle the number of regions has doubled.  It might be natural to think that this pattern will continue, and that if we add a fourth line then the sphere will be divided into sixteen regions.   Let’s add a new line and see.  The diagram is starting to get a little confusing!

Four great circles divide a sphere into 14 regions

Four great circles divide a sphere into 14 regions

Like in the previous diagram, you should see the red numbers as being written on the outside of the sphere, and the green numbers as written on the inside.  It looks like the doubling rule has turned out to be misleading — this sphere only has 14 regions, rather than the expected 16.

What happens when we keep adding circles?  We could try to make another diagram, but finding all the regions might be difficult! It seems easier to let reason take over at this point, and give the pictorial part of the brain a rest.

How can we do that?  One powerful fact we have is that two great circles intersect at two points.  It’s not quite clear how to use this, though.  Fortunately a lot of the hard thinking in this problem has already been done in the form of the Euler Characteristic.

We can define an intersection point of two great circles to be a vertex (V), and call any circular segment connecting two vertices an edge (E).  Then the regions bounded by edges will be called faces (F).  Euler’s polyhedron formula promises that our sphere (with any number of great circles) will always satisfy:

V-E+F = 2

So far we have:

Diagram 1:  V = E = 1 and F = 2

Diagram 2:  V = 2, E=4 and F = 4

Diagram 3: V = 6, E =12 and F =8

The values of V,E and F for the 4th diagram aren’t so obvious. Let’s try to figure them out carefully, so that our eyes don’t play tricks on us.

Pick one circle to focus on.  This intersects each of the other three circles in two places to generate 3×2=6 vertices.  Now, ignoring this circle and picking another circle, that circle intersects each of the remaining 2 circles in 2×2 = 4 new vertices.  Now throwing that circle out as well, there are two circles left, contributing a final 2 new vertices, for a total of 6+4+2 = 12 vertices.

We can count edges too.  Fix your attention on just one circle.  Notice that it should contain 6 vertices, two for each of the other three circles (because it intersects each of these twice.)  A circle with 6 points on it is divided into 6 pieces.  Therefore each circle contributes 6 edges, for a total of 4×6 = 24 edges.

I don’t know a simple way to reason out the number of faces, so let’s just say that by inspection we found that there were 14.

Notice that for each of the four diagrams, the Euler Characteristic formula for the sphere (vertices – edges+ faces = 2)

V-E+F = 2

 

applies:

1 - 1 + 2 = 2

 

2-4+4 = 2

 

6-12+8 = 2

 

12-24+14 = 2

 

Though counting faces seems to be hard, we can count edges and vertices for any number of circles fairly easily.  This means that we don’t need to count faces, because the Euler equation easily gives F = 2-V+E.  All we need to know is the formula for the number of edges E and the formula for the number of vertices V .

 

Following the reasoning we used for the 4th diagram, if there are n great circles, then the number of vertices will be

V = 2\cdot(n-1)+2\cdot(n-2)+\cdots+2 = 2\frac{(n-1)n}{2}

 

Similarly, there will be

E = n\cdot 2\cdot(n-1)

 

edges.  We can now find the number of faces by using the Euler Characteristic:

F = 2-V+E =2 - 2\frac{(n-1)n}{2} +n\cdot 2\cdot(n-1)

 

or

F = n^2-n+2

 

This tells us that the number of regions into which n great circles divide the sphere grows roughly as the square of the number of circles.  We can also compute particular values.  Though no one would probably ever want to count to check, with n = 100 great circles, there are 9902 regions.

This completely solves the problem of region counting with great circles on a sphere.  What’s next?

We now want to move away from the sphere for a moment and ask a seemingly unrelated question about arrangements of lines in the plane.

Just like we only used great circles in the sphere, we only want to consider “nice” arrangements of lines.  We don’t want any of our lines to be parallel, or any three of them to intersect at the same point.  Our line configurations are supposed to be “generic”– what you would get by picking a bunch of lines randomly.

 

Now, let’s try to play the region counting game with the plane.  Here are some pictures to get us started.

 

A line separates the plane into two regions

A line separates the plane into two regions

Two lines separate the plane into four

Two lines separate the plane into four

 

Three lines separate the plane into seven

Three lines separate the plane into seven

Four lines separate the plane into eleven
Four lines separate the plane into eleven

It’s clear that the plane is giving us values that are different from the sphere.  The numbers 1 (for no lines), 2, 4, 7, and 11 may at first seem to be random, but there is a subtle pattern.  These numbers can be seen as coming from Pascal’s triangle:

Pascal's triangle
Pascal’s triangle

In Pascal’s triangle, the entry in row n and column c comes from summing the entries directly above and to the left of it.  For example, 35 = 15+20, and 10 = 6+4.

We are looking for a way to connect the entries in the number sequence 1,2,4,7,11 to the entries in Pascal’s triangle.  We can do this as shown here:

Pascal's triangle, the first three columns
Pascal’s triangle, the first three columns emphasized

If you sum the elements in the first three columns in each row of Pascal’s triangle, it produces the number sequence 1,2,4,7,11,… which perfectly matches the sequence we got by making regions in the plane.  If you experiment, you will see that the pattern continues to work even for n > 4. Could this pattern give the number of regions in any arrangement of lines?

Our experience with trying to guess the number sequence for the number of regions in the sphere should have made us cautious.

How can we go about finding the formula for the number of regions made by n lines in the plane?

Maybe we can use the Euler characteristic again.  Unfortunately it’s not clear how, because the lines in the plane are infinite, and anyway if you check you can see that the formula

V-E+F=2

no longer seems to hold.  At the same time, it doesn’t seem like the plane is so different from the sphere.  In fact you can connect the two using a technique called stereographic projection.

Stereographic projection from the sphere to the plane

Stereographic projection gives a way to map the sphere onto the plane (which we imagine as being beneath the sphere).   The idea is that there is an infinitely tiny “lighthouse” located just at the north pole of the sphere. This tiny lighthouse shines through the sphere and “projects” all of its parts onto the plane beneath.  Notice that points on the sphere which are close to the north pole get sent very far away, and that the north pole itself never gets mapped to the plane.

What kinds of curves on the surface of the sphere will get mapped to lines in the plane? If you think about this for a second the answer will probably come to you:  circles (not necessarily great circles) on the surface of the sphere which pass through the north pole become lines in the projection:

Projecting circles from the sphere to the plane
Projecting circles from the sphere to the plane

This is difficult to draw, so please forgive my crude figure.  The diagram above shows two circles on the surface of the sphere being mapped to lines under stereographic projection.  The letters indicate how regions on the surface of the sphere (resulting from the arrangement of circles) translate to regions in the plane (resulting from the corresponding arrangement of lines. )

It is fun, to explore this line making machine.  How do you get parallel lines in the plane?  Perpendicular lines?  A moment’s thought should convince you that parallel lines in the plane “are” exactly the circles on the sphere that never intersect (except at the north pole).  Since we are only working with “nice” arrangements of lines, parallel lines are not allowed–we only need to be aware of them to avoid them.

It probably will not even occur to you to worry that the number of regions you get on the sphere with circles through the north pole is different than the number of regions you get in the plane with the corresponding lines.  The picture makes it pretty plain.  You can shore up your doubts by reflecting on the fact that stereographic projection is continuous, and so it preserves connectedness of things like line regions.

Now, we can answer our question about line regions in the plane by using the Euler Characteristic on the sphere again!  In fact, if we just remember to add one extra vertex (for the north pole) we can just count edges and vertices in the plane.

So our new planar formula is :

V+1-E + F = 2

or in other words

V -E + F = 1

Now, each line intersects each other line exactly once, and this breaks each of the n lines into n pieces.  Therefore

E = n\cdot n = n^2

The vertices can be counted as follows.  Fix one line.  It intersects each of the other n-1 lines.  This gives n-1 vertices.  Now discarding this line (to avoid double counting) and repeating this argument on the “next” line, we get n-2 more vertices. Continuing in this fashion, the number of vertices must be

V = n-1 + (n-2)+\cdots +2 +1 = \frac{(n-1)n}{2}

Putting everything together,

F = 1 - V + E = 1 - \frac{(n-1)n}{2} + n^2

or

F = \frac{n^2+n+2}{2}

This can also seen to be equal to the first three binomial coefficients \binom{n}{0}+\binom{n}{1} + \binom{n}{2}, confirming the conjecture about Pascal’s triangle.

This entry was posted in Uncategorized. Bookmark the permalink.

95 Responses to Circles, Lines and Regions

  1. The calculations were really complex and difficult to understand for the first time

  2. Thank you very much sir you made a great article I agree with you and I hope you will continue to make more articles like this Thank you so much sir

  3. Ayat Alkitab says:

    Thank you very much sir you made a great article I agree with you and I hope you will continue to make more articles like this Thank you so much sir

  4. sarah bakils says:

    Hi there,

    did you know this is a good and informative article, i like it. i will share this along to all my frind… you doing great job guys….

  5. Thanks for your information & good luck to you
    Resep Masakan

  6. دانلود آهنگ وای مامان ولم کن مگه گرفتمت میمیری نگی نگفتمت چالش اینستاگرام – – متن اهنگ Vay Maman Velom Kon جوان موزیک + new music اصلی کامل مامان ولم کن مگه گرفتمت jafar-171@
    ooo its cool

  7. Dedi Suarna says:

    thanks you for article

  8. Mom and Baby says:

    Good luck to you anda thanks for your information

  9. فروشگاه کاشانه

  10. آهنگ جدید گرشا رضایی مگه پاییز اومده Download New Music Garsha Rezaei – Mage Paeiz Oomade اهنگ اگه بارون بزنه با یاد تو دیوونه میشم مگه پاییز اومده jafar-167@

  11. I’m going to ramble on a bit about some fun pictorial counting games, with no particular point in mind, except to show some pretty relations.

  12. Gary says:

    دانلود جدید ترین قسمت سریال قبله عالم

    https://pishgammovie.ir/iranian-serial-download/ghebleh-alam/

  13. دانلود آهنگ های جدید ایرانی و خارجی شاد و ریمیکس آهنگ جدید jafar-158@ fit it now

  14. Mangalilu says:

    Good Information and thank you

  15. Androgeat says:

    Nice circle to project

  16. Jejakterkini says:

    The circle on the sphere in the figure is a complete

  17. دانلود آهنگ مازندرانی غمگین – اهنگ های عاشقانه غمگین مازندرانی جدید گلچین اهنگ های غمگین و شاد مازندرانی. آهنگ مازندرانی غمگین jafar-153@

  18. دانلود آهنگ چشم نظر از مجید رضوی با گیتار ریمیکس ورژن گیتار معروف عاشقانه احساسی برای همسر آهنگ چشم نظر مجید رضوی با گیتار jafar-109@ hum. ok im redy to learn it

  19. Loving the information on this website, you have done great job on the posts.

  20. دانلود آهنگ جدید سعید شریعت جنون – – متن اهنگ از Saeed Shariat Jonoon تابان موزیک + new music اصلی کامل tabanmusic.com سعید شریعت جنون jafar-126@ ooh nice learn. it is neccary.
    but a cant login to courses please check my payment

  21. دانلود آهنگ ریمیکس حرف اول اسمت گردن من تا ابد حمید حسام ریمیکس حرف اول اسمت jafar-125@

  22. Apkhebat says:

    Thank you very much sir you made a great article I agree with you.

  23. Romsmall says:

    Awesome article, thank you

  24. nana says:

    greatest
    goood luckk

  25. دانلود آهنگ ساسان آران شما آهنگ شما ساسان آران jafar-90@

  26. دانلود آهنگ سالگرد ازدواج عاشقانه آهنگ سالگرد ازدواج jafar-51@

  27. بهترین و بروز ترین منبع اهنگ های ایرانی و فرزاد فرزین آهنگ فرزاد فرزین jafar-93@

  28. دانلود نوحه جدید فارسی و سوزناک جدید ماه محرم 1400 دانلود نوحه جدید jafar-18@

  29. آهنگ شاد شمالی مازندرانی آهنگ شاد شمالی jafar-50@

  30. دانلود آهنگ های جدید ریمیکس ایرانی و ریمیکس خارجی باکیفیتبالا ریمیکس ماشین بیس دار آهنگ ریمیکس jafar-16@

  31. thanks for posting great

  32. duniaxtreme says:

    thanks for sharing

  33. دانلود آهنگ های تولدت مبارک دخترم و عاشقانه شاد دخترم تاج سرم آهنگ تولدت مبارک دخترم jafar-6@

  34. Thank you for some other magnificent article. The place else may just anybody get that type of information in such a perfect means of writing? I’ve a presentation next week, and I’m on the look for such information.

  35. Select Start > Programs or All Programs > Samsung Printers > Samsung Easy Document Creator > Samsung Easy Document Creator.
    The Samsung Easy Document Creator interface is comprised of various basic sections as described in the table that follows:
    Samsung Easy Printer Manager Download

  36. arief says:

    thank you very useful infogood informationI will try it.

  37. millers156 says:

    This website is designed for our students and families.

  38. Mikazo says:

    Thank you very much sir you made a great article I agree with you and I hope you will continue to make more articles Teknoyu

  39. via says:

    thanks for sharing

  40. Kekinian says:

    Great post thanks for sharing this information with up!

  41. aoifeawen says:

    Thankyou for your information gaes.. next again

  42. Log grader says:

    Infonya sangat menginspirasi

  43. nbice and hard work thanks for help
    jafar-63@

  44. Laptop rusak says:

    math very inportant on any science , but need more inteligence

  45. دانلود آهنگ شهرت ممدوف اوپوم نفسیندن آهنگ اوپوم نفسیندن jafar-27@

  46. Fasial Anwar says:

    Thank you, I like this information.

  47. دانلود آهنگ سلمان خان هندی جدید شاد رقص سلمان خان فیلم های هندی جدید 2020 شاد خفن تخیلی خواننده زن و رقص سلمان خان دانلود آهنگ سلمان خان e825130

  48. via says:

    Thank you sir.
    this is very helpful.
    thanks again sir

  49. sarah says:

    thanks boss.

    i like this post

  50. ajiprayoga says:

    Thank you great artikel

  51. Arul says:

    I have an math table for child. Thansk for sharing.

  52. Mas Awan says:

    Infonya sangat bermanfaat dan mengedukasi

  53. lab komputer says:

    helpfully blog for everyone…

  54. Pembelajaran yang sangat bermanfaat

  55. never read like this..nice article

  56. pulau seribu says:

    nice..i love to read it

  57. Thank you very much sir you made a great article I agree with you and I hope you will continue to make more articles like this Thank you so much sir
    Rerciver Option!

  58. sadra says:

    دانشمندان معتقدند گوش دادن موسیقی مناسب به افزایش تمرکز کمک میکند
    اما اینکه به چه مدل موسیقی گوش دهیم جای تفکر و بحث دارد.
    آهنگ کردی که از آهنگ های اصیل ایرانی است طرفدار بسیار دارد. با گوش دادن به موسیقی های اصیل ذهن خود را به کلمات اصیل و ناب بسپاریم .

  59. nice artikel good posting i read full of detail your grammar very perfect

  60. hai..its great to read

  61. thank you very much. this article is very helpful.

  62. آهنگ شاد کرمانجی عروسی دانلود جدیدترین آهنگ های کرمانجی دانلود آهنگ جدید و قدیمی کرمانجی دانلود اهنگ رقص و عروسی محلی کرمانجی جدیدترین آهنگهای کرمانجی آهنگ شاد کرمانجی عروسی 8f1de2c

  63. آهنگ جدید شاد با صدای خوانندگان برتر و پرطرفدار ایرانی به همراه ریمیکس شاد و بیس دار با بالاترین کیفیت ممکن # دانلود آهنگ شاد 9a3ae97

  64. آهنگ جدید شاد با صدای خوانندگان برتر و پرطرفدار ایرانی به همراه ریمیکس شاد و بیس دار با بالاترین کیفیت ممکن # آهنگ جدید شاد f93b683

  65. mojoshop says:

    thanks for good article

  66. mastimon says:

    thanks u for article

  67. Toko Bunga says:

    This website is designed for our students and families. It will provide information on what your child is learning in math, activities you can do at home to reinforce. Thanks

    Regards,
    Bunga Papan

  68. Thanks for your information & good luck to you

  69. Dompet Kulit says:

    I love this material :* thanks for share it Berita Teknologi

  70. Dompet Kulit says:

    I have matematik materi there Dompet Kulit

  71. Dompet Kulit says:

    greet artikel, I must studying it :v

  72. Pingback: The Won’t Stop Round Up : Footenotes

Comments are closed.