Diameter of a set

Last updated

Diameter of a set Diameter of a Set.svg
Diameter of a set

In mathematics, the diameter of a set of points in a metric space is the largest distance between points in the set. As an important special case, the diameter of a metric space is the largest distance between any two points in the space. This generalizes the diameter of a circle, the largest distance between two points on the circle. This usage of diameter also occurs in medical terminology concerning a lesion or in geology concerning a rock.

Contents

A bounded set is a set whose diameter is finite. Within a bounded set, all distances are at most the diameter.

Formal definition

The diameter of an object is the least upper bound (denoted "sup") of the set of all distances between pairs of points in the object. Explicitly, if is a set of points with distances measured by a metric , the diameter is [1] [2]

Of the empty set

The diameter of the empty set is a matter of convention. It can be defined to be zero, [2] [3] , [3] or undefined.

In Euclidean spaces

For any bounded set in the Euclidean plane or Euclidean space, the diameter of the object or set is the same as the diameter of its convex hull. For any convex shape in the plane, the diameter is the largest distance that can be formed between two opposite parallel lines tangent to its boundary. [4]

Relation to other measures

The diameter of a circle is exactly twice its radius. However, this is true only for a circle, and only in the Euclidean metric. Jung's theorem provides more general inequalities relating the diameter to the radius. [5] The isodiametric inequality or Bieberbach inequality, a relative of the isoperimetric inequality, states that, for a given diameter, the planar shape with the largest area is a disk, and the three-dimensional shape with the largest volume is a sphere. [6] [7] The polygons of maximum area for a given diameter and number of sides are the biggest little polygons. [8]

Just as the diameter of a two-dimensional convex set is the largest distance between two parallel lines tangent to and enclosing the set, the width is often defined to be the smallest such distance. [4] The diameter and width are equal only for a body of constant width, for which all pairs of parallel tangent lines have the same distance. Every set of bounded diameter in the Euclidean plane is a subset of a body of constant width with the same diameter. [9]

Computation

The diameter or width of a two-dimensional point set or polygon can be calculated efficiently using rotating calipers. [4] Algorithms for computing diameters in higher-dimensional Euclidean spaces have also been studied in computational geometry; see diameter (computational geometry).

In differential geometry

In differential geometry, the diameter is an important global Riemannian invariant. Every compact set in a Riemannian manifold, and every compact Riemannian manifold itself, has finite diameter. For instance, the unit sphere of any dimension, viewed as a Riemannian manifold, has diameter . This differs from its diameter as a subset of Euclidean space (which would equal two) because, as a Riemannian manifold, distances are measured along geodesics within the manifold. [10]

In a Riemannian manifold whose Ricci curvature has a positive constant lower bound, the diameter is also bounded by Myers's theorem. According to Cheng's maximal diameter theorem, the unique manifold with the largest diameter for a given curvature lower bound is a sphere with that curvature. The theorem is named after Shiu-Yuen Cheng, who published it in 1975. [10] [11]

In graphs

In graph theory, the diameter of a connected undirected graph is the farthest distance between any two of its vertices. That is, it is the diameter of a set, for the set of vertices of the graph, and for the shortest-path distance in the graph. Diameter may be considered either for weighted or for unweighted graphs. Researchers have studied the problem of computing the diameter, both in arbitrary graphs and in special classes of graphs.

Special cases of graph diameter include the diameter of a group, defined using a Cayley graph with the largest diameter possible for a given group, and the diameter of the flip graph of triangulations of a point set, the minimum number of local moves needed to transform one triangulation into another for two triangulations chosen to be as far apart as possible.

Related Research Articles

<span class="mw-page-title-main">Metric space</span> Mathematical space with a notion of distance

In mathematics, a metric space is a set together with a notion of distance between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting for studying many of the concepts of mathematical analysis and geometry.

<span class="mw-page-title-main">Convex hull</span> Smallest convex set containing a given set

In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

<span class="mw-page-title-main">Riemannian manifold</span> Smooth manifold with an inner product on each tangent space

In differential geometry, a Riemannian manifold is a geometric space on which many geometric notions such as distance, angles, length, volume, and curvature are defined. Euclidean space, the -sphere, hyperbolic space, and smooth surfaces in three-dimensional space, such as ellipsoids and paraboloids, are all examples of Riemannian manifolds. Riemannian manifolds are named after German mathematician Bernhard Riemann, who first conceptualized them.

Riemannian geometry is the branch of differential geometry that studies Riemannian manifolds, defined as smooth manifolds with a Riemannian metric. This gives, in particular, local notions of angle, length of curves, surface area and volume. From those, some other global quantities can be derived by integrating local contributions.

<span class="mw-page-title-main">Shing-Tung Yau</span> Chinese-American mathematician (born 1949)

Shing-Tung Yau is a Chinese-American mathematician. He is the director of the Yau Mathematical Sciences Center at Tsinghua University and professor emeritus at Harvard University. Until 2022, Yau was the William Caspar Graustein Professor of Mathematics at Harvard, at which point he moved to Tsinghua.

<span class="mw-page-title-main">Hyperbolic space</span> Non-Euclidean geometry

In mathematics, hyperbolic space of dimension n is the unique simply connected, n-dimensional Riemannian manifold of constant sectional curvature equal to −1. It is homogeneous, and satisfies the stronger property of being a symmetric space. There are many ways to construct it as an open subset of with an explicitly written Riemannian metric; such constructions are referred to as models. Hyperbolic 2-space, H2, which was the first instance studied, is also called the hyperbolic plane.

In mathematics, the isoperimetric inequality is a geometric inequality involving the square of the circumference of a closed curve in the plane and the area of a plane region it encloses, as well as its various generalizations. Isoperimetric literally means "having the same perimeter". Specifically, the isoperimetric inequality states, for the length L of a closed curve and the area A of the planar region that it encloses, that

This is a glossary of some terms used in Riemannian geometry and metric geometry — it doesn't cover the terminology of differential topology.

Myers's theorem, also known as the Bonnet–Myers theorem, is a celebrated, fundamental theorem in the mathematical field of Riemannian geometry. It was discovered by Sumner Byron Myers in 1941. It asserts the following:

In mathematics, more precisely in topology and differential geometry, a hyperbolic 3-manifold is a manifold of dimension 3 equipped with a hyperbolic metric, that is a Riemannian metric which has all its sectional curvatures equal to −1. It is generally required that this metric be also complete: in this case the manifold can be realised as a quotient of the 3-dimensional hyperbolic space by a discrete group of isometries.

<span class="mw-page-title-main">Systolic geometry</span> Form of differential geometry

In mathematics, systolic geometry is the study of systolic invariants of manifolds and polyhedra, as initially conceived by Charles Loewner and developed by Mikhail Gromov, Michael Freedman, Peter Sarnak, Mikhail Katz, Larry Guth, and others, in its arithmetical, ergodic, and topological manifestations. See also Introduction to systolic geometry.

Aleksei Vasilyevich Pogorelov, was a Soviet mathematician. Specialist in the field of convex and differential geometry, geometric PDEs and elastic shells theory, the author of novel school textbooks on geometry and university textbooks on analytical geometry, on differential geometry, and on the foundations of geometry.

In mathematics, the Cartan–Hadamard theorem is a statement in Riemannian geometry concerning the structure of complete Riemannian manifolds of non-positive sectional curvature. The theorem states that the universal cover of such a manifold is diffeomorphic to a Euclidean space via the exponential map at any point. It was first proved by Hans Carl Friedrich von Mangoldt for surfaces in 1881, and independently by Jacques Hadamard in 1898. Élie Cartan generalized the theorem to Riemannian manifolds in 1928. The theorem was further generalized to a wide class of metric spaces by Mikhail Gromov in 1987; detailed proofs were published by Ballmann (1990) for metric spaces of non-positive curvature and by Alexander & Bishop (1990) for general locally convex metric spaces.

In differential geometry, Mikhail Gromov's filling area conjecture asserts that the hemisphere has minimum area among the orientable surfaces that fill a closed curve of given length without introducing shortcuts between its points.

In Riemannian geometry, the filling radius of a Riemannian manifold X is a metric invariant of X. It was originally introduced in 1983 by Mikhail Gromov, who used it to prove his systolic inequality for essential manifolds, vastly generalizing Loewner's torus inequality and Pu's inequality for the real projective plane, and creating systolic geometry in its modern form.

In mathematics, a space, where is a real number, is a specific type of metric space. Intuitively, triangles in a space are "slimmer" than corresponding "model triangles" in a standard space of constant curvature . In a space, the curvature is bounded from above by . A notable special case is ; complete spaces are known as "Hadamard spaces" after the French mathematician Jacques Hadamard.

<span class="mw-page-title-main">Cut locus</span>

In differential geometry, the cut locus of a point p on a manifold is the closure of the set of all other points on the manifold that are connected to p by two or more distinct shortest geodesics. More generally, the cut locus of a closed set X on the manifold is the closure of the set of all other points on the manifold connected to X by two or more distinct shortest geodesics.

<span class="mw-page-title-main">Blaschke–Lebesgue theorem</span> Plane geometry theorem on least area of all curves of given constant width

In plane geometry the Blaschke–Lebesgue theorem states that the Reuleaux triangle has the least area of all curves of given constant width. In the form that every curve of a given width has area at least as large as the Reuleaux triangle, it is also known as the Blaschke–Lebesgue inequality. It is named after Wilhelm Blaschke and Henri Lebesgue, who published it separately in the early 20th century.

<span class="mw-page-title-main">Flip graph</span> A graph that encodes local operations in mathematics

In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are special cases of geometric graphs.

In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles in the triangulation and then adds the other diagonal in the edge's enclosing quadrilateral, forming a different triangulation of the same point set.

References

  1. Kaplansky, Irving (1977), Set Theory and Metric Spaces (2nd ed.), Chelsea Publishing, p. 69, ISBN   978-1-4704-6384-7, MR   0446980
  2. 1 2 Rado, T.; Reichelderfer, P. V. (1955), Continuous transformations in analysis. With an introduction to algebraic topology, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete, vol. LXXV, Springer-Verlag, p. 14, doi:10.1007/978-3-642-85989-2, ISBN   978-3-642-85991-5, MR   0079620
  3. 1 2 Capoyleas, Vasilis; Rote, Günter; Woeginger, Gerhard (1991), "Geometric clusterings", Journal of Algorithms , 12 (2): 341–356, doi: 10.1016/0196-6774(91)90007-L , MR   1105480
  4. 1 2 3 Toussaint, Godfried T. (1983), "Solving geometric problems with the rotating calipers" (PDF), Proc. MELECON '83: Mediterranean Electrotechnical Conference, 24–26 May 1983, Athens, IEEE, CiteSeerX   10.1.1.155.5671
  5. Burago, Yu. D.; Zalgaller, V. A. (1988), "11.1: Jung's ball and other covering bodies", Geometric Inequalities, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 285, translated by Sosinskiĭ, A. B., Berlin: Springer-Verlag, pp. 91–93, doi:10.1007/978-3-662-07441-1, ISBN   3-540-13615-0, MR   0936419, Zbl   0633.53002
  6. Littlewood, J. E. (1953), "An isoperimetrical problem", A Mathematicians Miscellany, Methuen, pp. 10–11
  7. Burago & Zalgaller 1988, p. 93.
  8. Foster, Jim; Szabo, Tamas (2007), "Diameter graphs of polygons and the proof of a conjecture of Graham", Journal of Combinatorial Theory, Series A , 114 (8): 1515–1525, doi: 10.1016/j.jcta.2007.02.006 , MR   2360684
  9. Klee, Victor (1971), "What is a convex set?", The American Mathematical Monthly , 78 (6): 616–631, doi:10.1080/00029890.1971.11992815, JSTOR   2316569, MR   0285985
  10. 1 2 Lee, John M. (2018), Introduction to Riemannian Manifolds, Graduate Texts in Mathematics, vol. 176 (2nd ed.), pp. 39, 345, 362, doi:10.1007/978-3-319-91755-9, ISBN   978-3-319-91755-9
  11. Cheng, Shiu Yuen (1975), "Eigenvalue comparison theorems and its geometric applications", Mathematische Zeitschrift , 143 (3): 289–297, doi:10.1007/BF01214381, MR   0378001