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, sometimes called Moser's circle problem, has a solution by an inductive method. The greatest possible number of regions, rG = , giving the sequence 1, 2, 4, 8, 16, 31, 57, 99, 163, 256, ... ( OEIS: A000127 ). Though the first five terms match the geometric progression 2n− 1, it deviates at n = 6, showing the risk of generalising from only a few observations.
If there are n points on the circle and one more point is added, n lines can be drawn 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. The new point A can be chosen so that case b occurs for each of the new lines.
Proof. For the case a, three points must be on one line: the new point A, the old point O to which the line is drawn, and the point I where two of the old lines intersect. 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.
The lemma establishes an important property for solving the problem. By employing an inductive proof, one can arrive at a formula for f(n) in terms of f(n − 1).
In the figure the dark lines are 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 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 being added. 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
points 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
Using the sums of the first natural numbers and the first squares, this combines to
Finally,
which yields
k n | 0 | 1 | 2 | 3 | 4 | Sum | |
---|---|---|---|---|---|---|---|
1 | 1 | — | — | — | — | 1 | |
2 | 1 | 1 | — | — | — | 2 | |
3 | 1 | 2 | 1 | — | — | 4 | |
4 | 1 | 3 | 3 | 1 | — | 8 | |
5 | 1 | 4 | 6 | 4 | 1 | 16 | |
6 | 1 | 5 | 10 | 10 | 5 | 31 | |
7 | 1 | 6 | 15 | 20 | 15 | 57 | |
8 | 1 | 7 | 21 | 35 | 35 | 99 | |
9 | 1 | 8 | 28 | 56 | 70 | 163 | |
10 | 1 | 9 | 36 | 84 | 126 | 256 | |
The series alternatively derived from the sum of up to the first 5 terms of each row of Pascal's triangle [1] |
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 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). 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 quadrilaterals, 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, only the interior vertices were enumerated, group 2 edges are counted twice while group 3 edges are counted once only.
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 resolves to
which yields the same quartic polynomial obtained by using the inductive method
The fifth column of Bernoulli's triangle (k = 4) gives the maximum number of regions in the problem of dividing a circle into areas for n + 1 points, where n≥ 4.
Considering the force-free motion of a particle inside a circle it was shown (see D. Jaud) that for specific reflection angles along the circle boundary the associated area division sequence is given by an arithmetic series.
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. The distance between any point of the circle and the centre is called the radius.
In mathematics, an ellipse is a plane curve surrounding two focal points, such that for all points on the curve, the sum of the two distances to the focal points is a constant. It generalizes a circle, which is the special type of ellipse in which the two focal points are the same. The elongation of an ellipse is measured by its eccentricity , a number ranging from to .
In mathematics, a hyperbola is a type of smooth curve lying in a plane, defined by its geometric properties or by equations for which it is the solution set. A hyperbola has two pieces, called connected components or branches, that are mirror images of each other and resemble two infinite bows. The hyperbola is one of the three kinds of conic section, formed by the intersection of a plane and a double cone. If the plane intersects both halves of the double cone but does not pass through the apex of the cones, then the conic is a hyperbola.
In geometry, a polygon is a plane figure made up of line segments connected to form a closed polygonal chain.
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. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
In geometry, bisection is the division of something into two equal or congruent parts. Usually it involves a bisecting line, also called a bisector. The most often considered types of bisectors are the segment bisector, a line that passes through the midpoint of a given segment, and the angle bisector, a line that passes through the apex of an angle . In three-dimensional space, bisection is usually done by a bisecting plane, also called the bisector.
In geometry, an altitude of a triangle is a line segment through a vertex and perpendicular to a line containing the side opposite the vertex. This line containing the opposite side is called the extended base of the altitude. The intersection of the extended base and the altitude is called the foot of the altitude. The length of the altitude, often simply called "the altitude", is the distance between the extended base and the vertex. The process of drawing the altitude from the vertex to the foot is known as dropping the altitude at that vertex. It is a special case of orthogonal projection.
In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any object in -dimensional Euclidean space.
In Euclidean geometry, a cyclic quadrilateral or inscribed 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. The center of the circle and its radius are called the circumcenter and the circumradius respectively. Other names for these quadrilaterals are concyclic quadrilateral and chordal quadrilateral, the latter since the sides of the quadrilateral are chords of the circumcircle. Usually the quadrilateral is assumed to be convex, but there are also crossed cyclic quadrilaterals. The formulas and properties given below are valid in the convex case.
In vector calculus, Green's theorem relates a line integral around a simple closed curve C to a double integral over the plane region D bounded by C. It is the two-dimensional special case of Stokes' theorem.
In four-dimensional geometry, the 24-cell is the convex regular 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol {3,4,3}. It is also called C24, or the icositetrachoron, octaplex (short for "octahedral complex"), icosatetrahedroid, octacube, hyper-diamond or polyoctahedron, being constructed of octahedral cells.
In geometry, the incenter of a triangle is a triangle center, a point defined for any triangle in a way that is independent of the triangle's placement or scale. The incenter may be equivalently defined as the point where the internal angle bisectors of the triangle cross, as the point equidistant from the triangle's sides, as the junction point of the medial axis and innermost point of the grassfire transform of the triangle, and as the center point of the inscribed circle of the triangle.
In geometry, a decagon is a ten-sided polygon or 10-gon. The total sum of the interior angles of a simple decagon is 1440°.
In Euclidean geometry, a regular polygon is a polygon that is direct equiangular and equilateral. Regular polygons may be either convex, star or skew. In the limit, a sequence of regular polygons with an increasing number of sides approximates a circle, if the perimeter or area is fixed, or a regular apeirogon, if the edge length is fixed.
In geometry, a diagonal is a line segment joining two vertices of a polygon or polyhedron, when those vertices are not on the same edge. Informally, any sloping line is called diagonal. The word diagonal derives from the ancient Greek διαγώνιος diagonios, "from angle to angle" ; it was used by both Strabo and Euclid to refer to a line connecting two vertices of a rhombus or cuboid, and later adopted into Latin as diagonus.
In geometry, the 5-cell is the convex 4-polytope with Schläfli symbol {3,3,3}. It is a 5-vertex four-dimensional object bounded by five tetrahedral cells. It is also known as a C5, pentachoron, pentatope, pentahedroid, or tetrahedral pyramid. It is the 4-simplex (Coxeter's polytope), the simplest possible convex 4-polytope, and is analogous to the tetrahedron in three dimensions and the triangle in two dimensions. The 5-cell is a 4-dimensional pyramid with a tetrahedral base and four tetrahedral sides.
In geometry, the 120-cell is the convex regular 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol {5,3,3}. It is also called a C120, dodecaplex (short for "dodecahedral complex"), hyperdodecahedron, polydodecahedron, hecatonicosachoron, dodecacontachoron and hecatonicosahedroid.
In geometry, a pentagon is any five-sided polygon or 5-gon. The sum of the internal angles in a simple pentagon is 540°.
In mathematics, the Schoenflies problem or Schoenflies theorem, of geometric topology is a sharpening of the Jordan curve theorem by Arthur Schoenflies. For Jordan curves in the plane it is often referred to as the Jordan–Schoenflies theorem.
In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of edge crossings in a plane drawing of a given graph, as a function of the number of edges and vertices of the graph. It states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e3/n2.