# 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

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 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

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

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

Two lines separate the plane into four

Three lines separate the plane into seven

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

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 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

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. amazing post

5. big hash says:

big hash web

6. fakaza says:

nice

7. 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….

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

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

10. Dedi Suarna says:

thanks you for article

11. Mom and Baby says:

Good luck to you anda thanks for your information

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

13. majid says:

beauty fulll

14. Gogoherbs supplements

15. vera says:

greatest post

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

17. 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.

18. Linda says:
19. Gary says:

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

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

21. Mangalilu says:

Good Information and thank you

22. Androgeat says:

Nice circle to project

23. Jejakterkini says:

The circle on the sphere in the figure is a complete

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

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

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

27. دانلود آهنگ جدید سعید شریعت جنون – – متن اهنگ از Saeed Shariat Jonoon تابان موزیک + new music اصلی کامل tabanmusic.com سعید شریعت جنون jafar-126@ ooh nice learn. it is neccary.

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

29. Apkhebat says:

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

30. Romsmall says:

Awesome article, thank you

31. Inspirasi_Ku says:

goood luckk

32. thanks for sharing

33. nana says:

greatest
goood luckk

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

35. دانلود آهنگ مرتضی سرمدی وابسته آهنگ وابسته مرتضی سرمدی jafar-86@

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

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

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

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

40. آهنگ مازندرانی لاتی تک دست زندونی آهنگ مازندرانی لاتی تک دست jafar-26@

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

42. thanks for posting great

43. duniaxtreme says:

thanks for sharing

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

45. 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.

46. 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:

47. arief says:

thank you very useful infogood informationI will try it.

48. millers156 says:

This website is designed for our students and families.

49. Labkom99 says:

Nice article

50. 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

51. vera says:

enjoy

52. via says:

thanks for sharing

53. Kekinian says:

Great post thanks for sharing this information with up!

54. aoifeawen says:

Thankyou for your information gaes.. next again

55. thanks u for article

Infonya sangat menginspirasi

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

58. Laptop rusak says:

math very inportant on any science , but need more inteligence

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

60. Fasial Anwar says:

Thank you, I like this information.

61. aio says:

thnaks

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

63. arif korek says:

thanks artikel

64. thanks for you sharing sir

65. via says:

Thank you sir.
thanks again sir

66. sarah says:

thanks boss.

i like this post

67. jimmy says:

thanks a lot sir

68. ajiprayoga says:

Thank you great artikel

69. Arul says:

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

70. Mas Awan says:

Infonya sangat bermanfaat dan mengedukasi

71. thanks u for article

72. lab komputer says:

73. Pembelajaran yang sangat bermanfaat

74. never read like this..nice article

75. pulau seribu says:

76. 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!

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

78. Bbnaija2020 says:

Amazing one

79. Good one

80. Nice one

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

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

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

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

87. mojoshop says:

thanks for good article

88. thanks u for article

89. mastimon says:

thanks u for article

90. 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

91. Thanks for your information & good luck to you

92. Dompet Kulit says:

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

93. Dompet Kulit says:

I have matematik materi there Dompet Kulit

94. Dompet Kulit says:

greet artikel, I must studying it :v

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