In the geometry of circle packings in the Euclidean plane, the ring lemma gives a lower bound on the sizes of adjacent circles in a circle packing. [1]
In the geometry of circle packings in the Euclidean plane, the ring lemma gives a lower bound on the sizes of adjacent circles in a circle packing. [1]
The lemma states: Let be any integer greater than or equal to three. Suppose that the unit circle is surrounded by a ring of interior-disjoint circles, all tangent to it, with consecutive circles in the ring tangent to each other. Then the minimum radius of any circle in the ring is at least the unit fraction where is the th Fibonacci number. [1] [2]
The sequence of minimum radii, from , begins
Generalizations to three-dimensional space are also known. [3]
An infinite sequence of circles can be constructed, containing rings for each that exactly meet the bound of the ring lemma, showing that it is tight. The construction allows halfplanes to be considered as degenerate circles with infinite radius, and includes additional tangencies between the circles beyond those required in the statement of the lemma. It begins by sandwiching the unit circle between two parallel halfplanes; in the geometry of circles, these are considered to be tangent to each other at the point at infinity. Each successive circle after these first two is tangent to the central unit circle and to the two most recently added circles; see the illustration for the first six circles (including the two halfplanes) constructed in this way. The first circles of this construction form a ring, whose minimum radius can be calculated by Descartes' theorem to be the same as the radius specified in the ring lemma. This construction can be perturbed to a ring of finite circles, without additional tangencies, whose minimum radius is arbitrarily close to this bound. [4]
A version of the ring lemma with a weaker bound was first proven by Burton Rodin and Dennis Sullivan as part of their proof of William Thurston's conjecture that circle packings can be used to approximate conformal maps. [5] Lowell Hansen gave a recurrence relation for the tightest possible lower bound, [6] and Dov Aharonov found a closed-form expression for the same bound. [2]
Beyond its original application to conformal mapping, [5] the circle packing theorem and the ring lemma play key roles in a proof by Keszegh, Pach, and Pálvölgyi that planar graphs of bounded degree can be drawn with bounded slope number. [7]
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 geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for the diameter of a sphere.
In mathematics, curvature is any of several strongly related concepts in geometry that intuitively measure the amount by which a curve deviates from being a straight line or by which a surface deviates from being a plane. If a curve or surface is contained in a larger space, curvature can be defined extrinsically relative to the ambient space. Curvature of Riemannian manifolds of dimension at least two can be defined intrinsically without reference to a larger space.
Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.
In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, spaces of other dimensions or to non-Euclidean spaces such as hyperbolic space.
In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another.
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
In mathematics, an Apollonian gasket or Apollonian net is a fractal generated by starting with a triple of circles, each tangent to the other two, and successively filling in more circles, each tangent to another three. It is named after Greek mathematician Apollonius of Perga.
In geometry, the midsphere or intersphere of a convex polyhedron is a sphere which is tangent to every edge of the polyhedron. Not every polyhedron has a midsphere, but the uniform polyhedra, including the regular, quasiregular and semiregular polyhedra and their duals all have midspheres. The radius of the midsphere is called the midradius. A polyhedron that has a midsphere is said to be midscribed about this sphere.
In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.
Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.
In geometry, Coxeter's loxodromic sequence of tangent circles is an infinite sequence of circles arranged so that any four consecutive circles in the sequence are pairwise mutually tangent. This means that each circle in the sequence is tangent to the three circles that precede it and also to the three circles that follow it.
The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:
Square packing is a packing problem where the objective is to determine how many congruent squares can be packed into some larger shape, often a square or circle.
In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex.
In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.
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.
In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.
Introduction to Circle Packing: The Theory of Discrete Analytic Functions is a mathematical monograph concerning systems of tangent circles and the circle packing theorem. It was written by Kenneth Stephenson and published in 2005 by the Cambridge University Press.
In the mathematics of circle packing, a Doyle spiral is a pattern of non-crossing circles in the plane in which each circle is surrounded by a ring of six tangent circles. These patterns contain spiral arms formed by circles linked through opposite points of tangency, with their centers on logarithmic spirals of three different shapes.
