Dividing a circle into areas
Encyclopedia
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 diagonal
s, has a solution by an inductive method.
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 old 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 each 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 n old points O, and hence finitely many points I where two of the old lines intersect. For each O and I, the line OI crosses the circle in one point other than O. Since the circle has infinitely many points, it has a point A which will be on none of the lines OI. Then, for this point A and all of the 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.
, one can provide a formula for f(n) in terms of f(n − 1).
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
points on the left and
on the right, so
a total of
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
Which can be easily reduced to
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.
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). As the graph is connected, the Euler relation for the 2-dimensional sphere S 2
holds. View the diagram (the circle together with all the chords) above as a planar graph. If the general formulas for V and E can both be found, the formula for F can also be derived, which will solve the problem.
Its vertices include the n points on the circle, referred to as the exterior vertices, as well as the interior vertices, the intersections of distinct chords in the interior of the circle. The "generic intersection" assumption made above guarantees that each interior vertex is the intersection of no more than two chords.
Thus the main task in determining V is finding the number of interior vertices. As a consequence of the lemma, any two intersecting chords will uniquely determine an interior vertex. These chords are in turn uniquely determined by the four corresponding endpoints of the chords, which are all exterior vertices. Any four exterior vertices determine a cyclic quadrilateral
, and all cyclic quadrilaterals are convex quadrilateral
s, so each set of four exterior vertices have exactly one point of intersection formed by their diagonals(chords). Further, by definition all interior vertices are formed by intersecting chords.
Therefore each interior vertex is uniquely determined by a combination of four exterior vertices, where the number of interior vertices is given by
and so
The edges include the n circular arcs connecting pairs of adjacent exterior vertices, as well as the chordal line segments (described below) created inside the circle by the collection of chords. Since there are two groups of vertices: exterior and interior, the chordal line segments can be further categorized into three groups:
To find the number of edges in groups 2 and 3, consider each interior vertex, which is connected to exactly four edges. This yields
edges. Since each edge is defined by two endpoint vertices, and we only enumerated the interior vertices, group 2 edges are counted twice while group 3 edges are counted once only.
Notice that every chord that is cut by another (i.e., chords not in group 1) must contain two group 3 edges, its beginning and ending chordal segments. As chords are uniquely determined by two exterior vertices, there are altogether
group 3 edges. This is twice the total number of chords that are not themselves members of group 1.
The sum of these results divided by two gives the combined number of edges in groups 2 and 3. Adding the n edges from group 1, and the n circular arc edges brings the total to
Substituting V and E into the Euler relation solved for F,
one then obtains
Since one of these faces is the exterior of the circle, the number of regions rG inside the circle is F − 1, or
which is the same quartic polynomial obtained by using the inductive method.
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, the problem of dividing a circle into areas by means of an inscribed polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
with n sides, in such a way as to maximise the number of areas created by the edges and diagonal
Diagonal
A diagonal is a line joining two nonconsecutive vertices of a polygon or polyhedron. Informally, any sloping line is called diagonal. The word "diagonal" derives from the Greek διαγώνιος , from dia- and gonia ; it was used by both Strabo and Euclid to refer to a line connecting two vertices of a...
s, has a solution by an inductive method.
Lemma
Lemma. We can choose the new point A so that case b occurs for each 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 n old points O, and hence finitely many points I where two of the old lines intersect. For each O and I, the line OI crosses the circle in one point other than O. Since the circle has infinitely many points, it has a point A which will be on none of the lines OI. Then, for this point A and all of the 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.
Inductive method
The lemma establishes an important property for solving the problem. By employing inductive proofMathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
, one can provide a formula for f(n) in terms of f(n − 1).
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
- n − i − 1
points on the left and
- i − 1 points
on the right, so
a total of
- (n − i − 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
Which can be easily reduced to
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.
Combinatorics and topology method
The lemma asserts that the number of regions is maximal if all "inner" intersections of chords are simple (exactly two chords pass through each point of intersection 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 characteristicEuler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent...
of a connected planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
(viewed here as a graph embedded in the 2-sphere
Sphere
A sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...
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). As the graph is connected, the Euler relation for the 2-dimensional sphere S 2
holds. View the diagram (the circle together with all the chords) above as a planar graph. If the general formulas for V and E can both be found, the formula for F can also be derived, which will solve the problem.
Its vertices include the n points on the circle, referred to as the exterior vertices, as well as the interior vertices, the intersections of distinct chords in the interior of the circle. The "generic intersection" assumption made above guarantees that each interior vertex is the intersection of no more than two chords.
Thus the main task in determining V is finding the number of interior vertices. As a consequence of the lemma, any two intersecting chords will uniquely determine an interior vertex. These chords are in turn uniquely determined by the four corresponding endpoints of the chords, which are all exterior vertices. Any four exterior vertices determine a cyclic quadrilateral
Cyclic quadrilateral
In Euclidean geometry, a cyclic quadrilateral is a quadrilateral whose vertices all lie on a single circle. This circle is called the circumcircle or circumscribed circle, and the vertices are said to be concyclic. Other names for these quadrilaterals are chordal quadrilateral and inscribed...
, and all cyclic quadrilaterals are convex quadrilateral
Quadrilateral
In Euclidean plane geometry, a quadrilateral is a polygon with four sides and four vertices or corners. Sometimes, the term quadrangle is used, by analogy with triangle, and sometimes tetragon for consistency with pentagon , hexagon and so on...
s, so each set of four exterior vertices have exactly one point of intersection formed by their diagonals(chords). Further, by definition all interior vertices are formed by intersecting chords.
Therefore each interior vertex is uniquely determined by a combination of four exterior vertices, where the number of interior vertices is given by
and so
The edges include the n circular arcs connecting pairs of adjacent exterior vertices, as well as the chordal line segments (described below) created inside the circle by the collection of chords. Since there are two groups of vertices: exterior and interior, the chordal line segments can be further categorized into three groups:
- Edges directly (not cut by other chords) connecting two exterior vertices. These are chords between adjacent exterior vertices, and form the perimeter of the polygon. There are n such edges.
- Edges connecting two interior vertices.
- Edges connecting an interior and exterior vertex.
To find the number of edges in groups 2 and 3, consider each interior vertex, which is connected to exactly four edges. This yields
edges. Since each edge is defined by two endpoint vertices, and we only enumerated the interior vertices, group 2 edges are counted twice while group 3 edges are counted once only.
Notice that every chord that is cut by another (i.e., chords not in group 1) must contain two group 3 edges, its beginning and ending chordal segments. As chords are uniquely determined by two exterior vertices, there are altogether
group 3 edges. This is twice the total number of chords that are not themselves members of group 1.
The sum of these results divided by two gives the combined number of edges in groups 2 and 3. Adding the n edges from group 1, and the n circular arc edges brings the total to
Substituting V and E into the Euler relation solved for F,
one then obtainsSince one of these faces is the exterior of the circle, the number of regions rG inside the circle is F − 1, or
which is the same quartic polynomial obtained by using the inductive method.