Diameter of a set

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.

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 ${\displaystyle S}$ is a set of points with distances measured by a metric ${\displaystyle \rho }$, the diameter is[1][2] $${\displaystyle \operatorname {diam} (S)=\sup _{x,y\in S}\rho (x,y).}$$

Of the empty set

The diameter of the empty set is a matter of convention. It can be defined to be zero,[2][3] ${\displaystyle -\infty }$,[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

Main article: Diameter (computational geometry)

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 ${\displaystyle \pi }$. 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

Main article: Diameter (graph theory)

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.

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. 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. 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. 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. 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