Dividing a circle into areas

In geometry, the problem of dividing a circle into areas by means of an inscribed polygon with n sides, in such a way as to maximise the number of areas created by the edges and diagonals, has a solution by an inductive method.

Contents

The problem

Suppose you have a circle with n points lying on the perimeter of the circle and lines connecting all of the points. There are a total of

<math>l(n)=\frac{n(n-1)}{2}<math>

lines connecting the points. The mission is to find the maximum number f(n) of areas that the circle can be divided into, as a function of the number n of points.

For small values we have:

  • n = 0 or 1 gives f(0) = f(1) = 1;
  • f(2) = 2 because there is a single diameter, making two areas;
  • f(3) = 4;
  • f(4) = 8,

and

f(5) = 16.

It is tempting to conjecture that

<math>f(n) = 2^{n-1}<math>.

But f(6) = 31.

Lemma

Missing image
DividingACircleIntoAreas-Box.png
Lemma

If we already have n points on the circle and add one more point, we draw n lines from the new point to previously existing points. Two cases are possible. In the first case (a), the new line passes through a point where two or more of lines between previously existing points cross. In the second case (b), the new line crosses each of the old lines in a different point. It will be useful to know the following fact.

Lemma. We can choose the new point A so that case b occurs for every of the new lines.

Proof. Notice that, for the case a, three points must be on one line: the new point A, the old point O to which we draw the line and the point I where two of the old lines intersect. Notice that there are finitely many (n) old points O, finitely many points I where two of the old lines intersect and, for each O and I, the line OI crosses the circle in one point other than O. Since the circle has infinitely many points, there is a point A which will be on none of lines OI. Then, for this point A and every of old points O, case b will be true.

This lemma means that, if there are k lines crossing AO, then each of them crosses AO at a different point and k+1 new areas are created by the line AO.

Proof

And here we go. This will be an inductive proof, providing a formula for f(n) in terms of f(n − 1).

Proof

In the figure you can see the dark lines connecting points 1 through 4 dividing the circle into 8 total regions (i.e., f(4) = 8). This figure illustrates the inductive step from n = 4 to n = 5 with the dashed lines. When the fifth point is added (i.e., when computing f(5) using f(4)), this results in four (n − 1) new lines (the dashed lines in the diagram) being added, numbered 1 through 4, one for each point that they connect to. The number of new regions introduced by the fifth point can therefore be determined by considering the number of regions added by each of the 4 lines. Set i to count the lines we are adding. Each new line can cross a number of existing lines, depending on which point it is to (the value of i). The new lines will never cross each other, except at the new point.

The number of lines that each new line intersects can be determined by considering the number of points on the "left" of the line and the number of points on the "right" of the line. Since all existing points already have lines between them, the number of points on the left multiplied by the number of points on the right is the number of lines that will be crossing the new line. For the line to point i, there are

ni − 1

points on the left and

i − 1 points

on the right, so a total of

(ni − 1)(i − 1)

lines must be crossed.

In this example, the lines to i = 1 and i = 4 each cross zero lines, while the lines to i = 2 and i = 3' each cross two lines (there are two points on one side and one on the other).

So the recurrence can be expressed as

<math>f(n)=f(n-1)+\sum^{n-1}_{i=1}\left(1+\left(n-i-1\right)\left(i-1\right)\right).<math>

Which can be easily reduced somewhat to

<math>f(n)=f(n-1)+\sum^{n-1}_{i=1}\left(2-n+ni-i^2\right)<math>
<math>=f(n-1)-n^2+3n-2+\sum^{n-1}_{i=1}\left(ni-i^2\right)<math>

This can be further reduced, using the formula for Σ i2.

It follows that the solution will be a quartic polynomial in n. Its actual coefficients can be found, by using the five values of f(n) given above.

Discussion of an alternate method

One part of the theorem asserts that the number of regions is maximal if all "inner" intersections of two different chords are simple (exactly two chords pass through a point of intersection of chords Q in the interior). This will be the case if the points on the circle are chosen "in general position". Under this assumption of "generic intersection", the number of regions can also be determined in a non-inductive way, using the formula for the Euler characteristic of a connected planar graph (viewed here as a graph embedded in the 2-sphere S 2).

A planar graph determines a cell decomposition of the plane with f faces (2-dimensional cells), e edges (1-dimensional cells) and v vertices (0-dimensional cells). If the graph is connected then the Euler relation for the 2-dimensional sphere S 2

<math>\, v-e+f=2

<math> holds. View the diagram (the circle together with all the chords) above as a planar graph G whose edges are the chordal line segments (connecting two "neighbouring" points of intersection of chords) created inside the circle by the collection of

<math> {{n(n-1)}\over 2} <math>

chords together with the n circular arcs connecting two adjacent points

<math>\, P_i <math> and <math>\, P_{(i+1)\, \mbox{mod}\, n} <math>.

Its vertices are the n points <math>\, P_i <math> together with the points <math>\, Q_i <math> given as the intersection of two (or more) chords in the interior of the circle. Under the "generic intersection" assumption made above exactly two chords pass through a point <math>\, Q_i <math>.

Call the number of interior points <math> v_{\mbox{interior}} <math>. Then the graph G' has

<math> v=v_{\mbox{interior}}+n <math>

vertices. The number of edges e can be determined using the general degree relation

<math> \sum_{v \in V(G)} d_v =2e <math>

valid for any (unordered) loop-free graph G with set of vertices V(G). Here for a vertex v of the graph <math> d_v <math> denotes the degree of the vertex (number of edges incident with v).

In the given graph the vertices <math>\, P_i <math> have degree

<math> n-1+2=n+1 <math>

(where the 2 corresponds to the two circular arcs emanating from <math>\, P_i <math>). All interior vertices <math>\, Q_i <math> have degree four (because exactly two chords pass through <math>\, Q_i <math>). This gives the relation

<math>\, 4v_{\mbox{interior}}+n(n+1)=2e <math>

or

<math> e=2v_{\mbox{interior}}+{{n(n+1)}\over 2} \ .<math>

Substituting this formula into the Euler relation solved for f, <math>\, f=e-v+2 <math>, one obtains then

<math> f=2v_{\mbox{interior}}+{{n(n+1)}\over 2}-(v_{\mbox{ interior}}+n)+2 <math>

or

<math> f=v_{\mbox{interior}}+{{n(n-1)}\over 2}+2 \ .<math>

The number of regions rG inside the circle is then

f − 1

(the outer region of the circle also counts as a face). Summarizing one finds that

<math> r_G=v_{\mbox{interior}}+{{n(n-1)}\over 2}+1 \ .

<math>

It remains to determine the total number of interior intersection points <math> v_{\mbox{interior}} <math>. In the following discussion we will assume that the points <math>\, P_i <math> have been numbered in counterclockwise increasing order (after choosing some of the points as <math>\, P_1 <math>). A pair of chords may be viewed as a "doubled" pair

<math>\, ((i_1,j_1), (i_2,j_2)) <math>:

where

<math> i_1

if the two chords have vertices <math> P_{i_1},P_{j_1} <math> and <math> P_{i_2},P_{j_2}<math> respectively. An interior intersection point uniquely determines an (unordered) pair of chords

<math> \,\{(i_1,j_1), (i_2,j_2)\}, \; i_1 < i_2 <math>,

under the assumption of "generic intersection". Under the condition <math>\, i_1 < i_2 <math> the two chords intersect (in the interior) if and only if

<math>\, i_2 < j_1 < j_2<math>;

in addition the four indices must be pairwise different. But any 4-element-subset

<math>\, \{ k_1,k_2,k_3,k_4 \}, \; \; k_1

of the set <math> \{1, \ldots, n\} <math> uniquely determines such an interlacing pair, namely

<math>\,((k_1,k_3), (k_2,k_4)) <math>

(which corresponds to the pair of chords in the quadrilateral with vertices <math> P_{k_i} <math>). Therefore

<math> v_{\mbox{interior}} ={n \choose 4}={{n(n-1)(n-2)(n-3)}\over 24}\ .

<math> Finally one obtains

<math> r_G ={n \choose 4}+{n \choose 2}+1

<math> which is the quartic polynomial determined in the inductive proof.

References

Conway, J. H. and Guy, R. K. "How Many Regions." In The Book of Numbers. New York: Springer-Verlag, pp. 76-79, 1996.

External links

Navigation

  • Art and Cultures
    • Art (https://academickids.com/encyclopedia/index.php/Art)
    • Architecture (https://academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (https://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (https://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools