Fact-checked by Grok 2 weeks ago

Convex geometry

Convex geometry is a branch of mathematics dedicated to the study of convex sets in Euclidean space, where a convex set is defined as any set that contains the entire line segment joining any two points within it. This field primarily examines compact convex subsets with nonempty interiors, known as convex bodies, and their properties such as volumes, sections, and inequalities.^[1]^[2] Key concepts in convex geometry include the convex hull, the smallest convex set containing a given set of points, formed by all convex combinations of those points, and extreme points, which are points in a convex set that cannot be expressed as a nontrivial convex combination of other points.^[2]^[3] Carathéodory's theorem states that in \mathbb{R}^d, any point in the convex hull of a set can be represented as a convex combination of at most d+1 points from that set, while Minkowski's theorem asserts that a compact convex set is the convex hull of its extreme points.^[3]^[2] The discipline addresses fundamental inequalities, such as the Brunn-Minkowski inequality, which relates the volumes of Minkowski sums of convex bodies and underpins much of modern convex geometry, including asymptotic behaviors in high dimensions.^[1]^[3] Fritz John's theorem guarantees that every convex body contains a unique ellipsoid of maximal volume, providing bounds on how closely convex bodies approximate ellipsoids, with applications in approximation theory and optimization.^[1] Dvoretzky's theorem further highlights that high-dimensional convex bodies possess nearly Euclidean subspaces, connecting convex geometry to functional analysis and probability.^[1] Convex geometry finds applications across mathematics and related fields, including linear programming through the analysis of polytopes—bounded polyhedra defined by finitely many inequalities—and in computer science for algorithmic problems like computing convex hulls.^[2]^[3] It also intersects with discrete geometry in the study of lattice points within convex bodies and with convex analysis via support functions and mixed volumes, which quantify interactions between multiple convex sets.^[3] The Hahn-Banach separation theorem ensures that disjoint convex sets can be separated by hyperplanes, a cornerstone for duality and optimization techniques.^[1]

Fundamentals

Convex Sets

In convex geometry, a set C in a real vector space is defined as convex if, for any two points x, y \in C and any scalar \lambda \in [0, 1], the point \lambda x + (1 - \lambda)y also belongs to C. This condition ensures that the entire line segment connecting x and y is contained within C, capturing the essence of sets that are "filled in" without gaps along straight paths.^[4]^[5] Geometrically, convex sets exhibit no concavities, dents, or holes; they can be visualized as shapes that are either smoothly rounded, like balls, or bounded by straight edges, like polyhedra, where every pair of points allows an unobstructed straight-line connection inside the set. This property distinguishes convex sets as the foundational building blocks for many results in optimization and analysis, providing a structure amenable to linear interpolation.^[4] Common examples illustrate this definition clearly. On the real line, any closed interval [a, b] is convex, as the segment between any two points within it remains inside. In Euclidean space \mathbb{R}^n, the closed ball \{ x \mid \|x - c\|_2 \leq r \} centered at c with radius r > 0 is convex, containing all points within and on its boundary. Half-spaces, defined by linear inequalities such as \{ x \mid a^T x \leq b \} with a \neq 0, are convex, as are polyhedra formed by finite intersections of half-spaces, like the set \{ x \mid A x \leq b \} for a matrix A and vector b.^[4] In contrast, non-convex sets violate this line-segment property. A torus in \mathbb{R}^3, which forms a doughnut shape with a central hole, is non-convex because the straight line between certain points on its surface passes through the empty interior. Similarly, a crescent-shaped region or any set with inward dents, such as a kidney bean outline, fails convexity, as line segments between boundary points may exit the set. These examples highlight how even minor indentations disrupt the required inclusion of intermediate points.^[4] The convex hull of a non-convex set provides the smallest convex set containing it, effectively "filling in" any violations of the convexity condition.^[4]

Convex Hull

The convex hull of a set S, denoted \operatorname{conv}(S), is defined as the smallest convex set containing S.^[6] This set can equivalently be characterized as the collection of all convex combinations of points from S, where a convex combination is a finite sum \sum_{i=1}^k \lambda_i x_i with x_i \in S, \lambda_i \geq 0, and \sum_{i=1}^k \lambda_i = 1.^[6] By construction, \operatorname{conv}(S) is itself convex, as it inherits the convexity property from the underlying combinations.^[7] One key property of the convex hull is that it coincides with the intersection of all convex sets that contain S.^[8] This intersection representation underscores its minimality: any convex set enclosing S must include \operatorname{conv}(S), and conversely, \operatorname{conv}(S) suffices as the tightest such enclosure.^[8] In \mathbb{R}^n, the convex hull of a finite set of points specifically yields a convex polytope, which serves as a foundational object in computational geometry for representing bounded convex regions. In terms of construction, for compact sets in Euclidean space, \operatorname{conv}(S) can be formed through finite convex combinations of points from S, leveraging the compactness to ensure closure under such operations.^[9] The Krein-Milman theorem further elaborates this for compact convex sets, stating that such a set equals the closed convex hull of its extreme points, though the full proof lies beyond the scope here.^[10]

Convex Combinations

A convex combination of a finite collection of points x_1, \dots, x_k in a real vector space is a linear combination \sum_{i=1}^k \lambda_i x_i, where the coefficients \lambda_i are nonnegative real numbers that sum to one, i.e., \lambda_i \geq 0 for all i and \sum_{i=1}^k \lambda_i = 1.^[11]^[12] A subset C of a vector space is convex if and only if it contains all convex combinations of its points.^[12] The convex hull of a set S, which is the smallest convex set containing S, consists precisely of all such finite convex combinations of points from S.^[11]^[12] In the context of simplices, convex combinations provide barycentric coordinates, which uniquely express any point inside a simplex as a weighted average of its vertices.^[13] For example, in a triangle with vertices A, B, and C, any interior point P can be written as P = \alpha A + \beta B + \gamma C where \alpha, \beta, \gamma \geq 0 and \alpha + \beta + \gamma = 1, with these coefficients representing the relative areas of the sub-triangles formed by P.^[13] This representation relies on the vertices being affinely independent, meaning that the differences between them (e.g., B - A and C - A) are linearly independent, ensuring the uniqueness of the combination.^[14]^[13] Carathéodory's theorem establishes a bound on the number of points needed in such representations within the convex hull.^[15] Specifically, in \mathbb{R}^n, every point in the convex hull of a set S can be expressed as a convex combination of at most n+1 points from S.^[15]^[12] The proof proceeds by considering an augmented set in \mathbb{R}^{n+1} and applying a result on positive combinations of linearly independent vectors, reducing any representation with more than n+1 points to one with fewer via linear dependence arguments.^[15]

Convex Functions

Definitions and Properties

A convex function is defined on a convex domain C \subseteq \mathbb{R}^n as a real-valued function f: C \to \mathbb{R} satisfying the inequality f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y) for all x, y \in C and \lambda \in [0,1]. Equivalently, f is convex if its epigraph \operatorname{epi}(f) = \{(x, t) \in C \times \mathbb{R} \mid t \geq f(x)\} is a convex set. The function is strictly convex if the inequality is strict whenever x \neq y and \lambda \in (0,1). Convex functions exhibit several elementary properties. The epigraph characterization directly implies that convexity is preserved under pointwise supremum, as the epigraph of the supremum is the intersection of the epigraphs. Midpoint convexity, where the inequality holds for \lambda = 1/2, implies full convexity provided f is continuous. Convex functions are locally Lipschitz continuous on the interior of their domain, meaning for each interior point there exists a neighborhood where |f(x) - f(y)| \leq L \|x - y\| for some constant L > 0. Additionally, the sum of convex functions is convex, and the composition f \circ g is convex if f is convex and nondecreasing and g is convex. Convex functions achieve their minimum over a compact convex set, as the sublevel sets are closed and bounded under continuity assumptions. Common examples include norms \| \cdot \|, which satisfy the triangle inequality implying convexity. Quadratic forms f(x) = x^T A x where A is positive semidefinite are convex, and strictly convex if A is positive definite. The exponential function f(x) = e^x is strictly convex, as its second derivative is positive. The sublevel sets \{x \in C \mid f(x) \leq \alpha\} of a convex function f are convex for any \alpha \in \mathbb{R}, following directly from the definition.

Jensen's Inequality

Jensen's inequality is a fundamental result in convex analysis that relates the value of a convex function at an average point to the average of the function values. For a convex function f: \mathbb{R}^n \to \mathbb{R} defined on a convex set and a probability measure \mu on \mathbb{R}^n, the inequality states that

\int f \, d\mu \geq f\left( \int \, d\mu \right),

provided the integrals exist.^[16] This continuous version generalizes the discrete case: for points x_1, \dots, x_k \in \dom f and weights \theta_1, \dots, \theta_k \geq 0 with \sum \theta_i = 1,

f\left( \sum_{i=1}^k \theta_i x_i \right) \leq \sum_{i=1}^k \theta_i f(x_i).

^[17] Equality holds if f is affine on the convex hull of the support or if all points are identical.^[17] A proof of the discrete form proceeds by induction on the number of terms k. For k=1, the inequality is trivial since \theta_1 = 1. Assume it holds for k-1 terms; for k terms, group the last two as a convex combination and apply the induction hypothesis to the resulting k-1 effective points.^[18] Alternatively, the inequality follows from the convexity of the epigraph of f, \epi f = \{ (x, t) \mid t \geq f(x) \}: the point \left( \sum \theta_i x_i, \sum \theta_i f(x_i) \right) lies in \epi f, so \sum \theta_i f(x_i) \geq f\left( \sum \theta_i x_i \right).^[17] The continuous version extends this via approximation by finite sums or direct use of the epigraph's convexity under integration.^[17] One key consequence is the arithmetic mean-geometric mean (AM-GM) inequality for positive real numbers x_1, \dots, x_k > 0 and weights \theta_i \geq 0 summing to 1:

\sum_{i=1}^k \theta_i x_i \geq \prod_{i=1}^k x_i^{\theta_i},

with equality if all x_i are equal. This follows from the convexity of g(t) = -\log t on (0, \infty), applying Jensen's inequality to yield \sum \theta_i \log x_i \leq \log \left( \sum \theta_i x_i \right), and exponentiating both sides.^[19] Jensen's inequality also yields moment inequalities; for example, since h(x) = |x|^p is convex for p \geq 1, \mathbb{E}[|X|^p] \geq |\mathbb{E}[X]|^p for a random variable X.^[17] The inequality extends naturally to concave functions: if f is concave, then \int f \, d\mu \leq f\left( \int \, d\mu \right), obtained by applying the convex case to -f.^[17]

Subgradients

In convex analysis, a vector g is a subgradient of a convex function f at a point x in its domain if it satisfies the inequality f(y) \geq f(x) + \langle g, y - x \rangle for all y in the domain, providing a linear underestimator of f that supports the epigraph at (x, f(x)).^[5] This definition generalizes the gradient for non-differentiable convex functions, where the subgradient captures the range of possible "slopes" consistent with convexity.^[5] The subdifferential \partial f(x) is the set of all subgradients g at x, forming a convex set that is nonempty for any proper convex f at interior points of its domain.^[5] If f is Lipschitz continuous in a neighborhood of x, then \partial f(x) is compact (bounded and closed).^[5] For a convex function f that is differentiable at x, the subdifferential reduces to the singleton \partial f(x) = \{\nabla f(x)\}, aligning with classical calculus.^[5] The subdifferential operator \partial f is monotone, meaning that for any x, y in the domain and u \in \partial f(x), v \in \partial f(y), the inequality \langle u - v, x - y \rangle \geq 0 holds; in fact, for proper lower semicontinuous convex functions, \partial f is maximally monotone.^[5] This monotonicity property underscores the role of subgradients in variational inequalities and monotone operator theory.^[5] A classic example is the absolute value function f(x) = |x| in one dimension, where the subdifferential at x = 0 is the interval \partial f(0) = [-1, 1], reflecting the non-differentiability at the origin, while \partial f(x) = \{\operatorname{sign}(x)\} for x \neq 0.^[5] For a norm \|\cdot\| on a vector space, the subdifferential at a nonzero x consists of elements g in the dual space such that \langle g, x \rangle = \|x\| and \|g\|_* \leq 1, where \|\cdot\|_* is the dual norm; at x = 0, it is the unit ball of the dual norm.^[5] Geometrically, subgradients correspond to outward normals of supporting hyperplanes to the epigraph, linking to separation theorems in convex geometry.^[5]

Separation and Supporting Hyperplanes

Hahn-Banach Separation Theorem

The Hahn-Banach theorem, in its analytic form, asserts that linear functionals defined on subspaces of real vector spaces can be extended to the entire space while preserving certain bounds. Specifically, let X be a real vector space, p: X \to \mathbb{R} a sublinear functional (satisfying p(x + y) \leq p(x) + p(y) and p(tx) = t p(x) for t \geq 0), Y \subset X a subspace, and \ell: Y \to \mathbb{R} a linear functional such that \ell(y) \leq p(y) for all y \in Y. Then there exists a linear functional f: X \to \mathbb{R} extending \ell (i.e., f|_Y = \ell) with f(x) \leq p(x) for all x \in X.^[20] This extension property is foundational, as it enables the construction of separating hyperplanes from bounded functionals on subspaces.^[21] The geometric form, known as the Hahn-Banach separation theorem, derives from the analytic version and provides a criterion for separating disjoint convex sets by hyperplanes. In a real topological vector space X, if A and B are nonempty convex subsets with A \cap B = \emptyset and A open, then there exist a continuous linear functional \phi: X \to \mathbb{R} and \alpha \in \mathbb{R} such that \phi(a) < \alpha \leq \phi(b) for all a \in A, b \in B.^[20] This strict separation holds because the openness of A ensures the hyperplane \{x \in X \mid \phi(x) = \alpha\} lies between the sets, with A entirely on one open half-space and B on the closed opposite half-space.^[22] The theorem applies to convex sets, which are subsets closed under convex combinations, allowing the functional to distinguish points outside one set from those inside the other.^[23] A supporting hyperplane to a convex set C at a boundary point x \in C is a hyperplane passing through x such that C lies entirely in one of the closed half-spaces it defines. Such hyperplanes exist by applying the Hahn-Banach separation theorem to separate C from points exterior to it, ensuring the set does not cross the hyperplane.^[5] The theorem holds in real vector spaces without requiring topology for the basic analytic extension, though the geometric separation typically assumes a topological structure (e.g., normed or locally convex spaces) to ensure continuity of the separating functional.^[20] No completeness or finite dimensionality is needed, making it applicable to general settings like Banach spaces.^[24] A proof of the analytic form proceeds by Zorn's lemma to obtain a maximal extension. Consider the partially ordered set of pairs (M, f), where M \supset Y is a subspace and f: M \to \mathbb{R} is linear with f|_Y = \ell and f(m) \leq p(m) for m \in M, ordered by inclusion of subspaces and agreement on restrictions. By Zorn's lemma, a maximal element (Z, \psi) exists. If Z \neq X, select x_0 \notin Z and extend to the one-dimensional enlargement V = Z \oplus \mathbb{R} x_0 by choosing a scalar \lambda such that \sup_{z \in Z} [\psi(z) - p(z - x_0)] \leq \lambda \leq \inf_{z \in Z} [p(z + x_0) - \psi(z)], which is a nonempty real interval; define \tilde{\psi}(z + t x_0) = \psi(z) + t \lambda for t \in \mathbb{R}, ensuring \tilde{\psi} \leq p on V and yielding a contradiction to maximality. Thus, Z = X and \psi is the desired extension.^[20] The geometric version follows by applying the analytic form to a suitable subspace generated by a point outside the convex set and using supporting hyperplanes at boundaries.^[22]

Strict and Non-Strict Separation

In convex geometry, non-strict separation, also known as proper separation, occurs when a hyperplane H = \{ x \in \mathbb{R}^n \mid a^T x = b \} with a \neq 0 bounds two closed half-spaces such that one disjoint convex set C satisfies a^T x \leq b for all x \in C, while the other disjoint convex set D satisfies a^T x \geq b for all x \in D. This allows the sets to touch the hyperplane but not cross it, providing a weak barrier between them. Such separation is guaranteed for any two nonempty disjoint convex sets in \mathbb{R}^n, as established by the separating hyperplane theorem, which relies on the Hahn-Banach theorem for its proof in finite dimensions. Strict separation strengthens this condition by requiring the sets to lie in open half-spaces, meaning a^T x < b for all x \in C and a^T x > b for all x \in D, ensuring a positive distance gap across the hyperplane. In \mathbb{R}^n, strict separation holds for two nonempty disjoint convex sets if at least one is compact and the other is closed, since compactness prevents asymptotic approach at infinity. Without compactness, strict separation may fail even for closed disjoint convex sets, as the sets can converge toward each other in unbounded directions despite remaining disjoint. In more general locally convex topological vector spaces, non-strict separation is always possible for two nonempty disjoint convex sets, one of which is closed, extending the finite-dimensional result via the Hahn-Banach separation theorem. Strict separation in such spaces requires additional conditions, such as one set being compact, to ensure the open half-spaces fully contain the sets without boundary contact. A classic example of strict separation is two disjoint closed balls in \mathbb{R}^n, where the compact nature of both allows a hyperplane midway between their centers to place each strictly in an open half-space. For non-strict separation without strict possibility, consider the disjoint closed convex sets C = \{ (x,y) \in \mathbb{R}^2 \mid y \geq 0 \} (the closed upper half-plane) and D = \{ (x,y) \in \mathbb{R}^2 \mid y \leq -e^{-x^2} \} (the region below a Gaussian curve); a horizontal hyperplane at y = 0 separates them non-strictly, as D lies below and touches asymptotically, but no hyperplane achieves strict separation due to the narrowing gap as |x| \to \infty. Parallel lines in \mathbb{R}^2, such as y = 0 and y = 1, admit strict separation by the line y = 0.5, illustrating a case where both types are possible since the sets are "bounded" in the transverse direction.

Applications to Convexity Proofs

Separation theorems provide powerful tools for establishing fundamental properties of convex sets. One key result is that every closed convex set in Euclidean space is the closure of its relative interior. To see this, suppose C \subseteq \mathbb{R}^n is a nonempty closed convex set. For any point x \in C, if x lies in the relative interior \operatorname{ri} C, it is already in the interior relative to the affine hull. Otherwise, since C has nonempty relative interior (as it is closed and convex), there exists a point y \in \operatorname{ri} C. The line segment between y and x must lie in C by convexity, and all points on this segment except possibly x belong to \operatorname{ri} C. Thus, x is a limit point of \operatorname{ri} C, implying \operatorname{cl}(\operatorname{ri} C) = C. This relies on the topological simplicity of convex sets, underpinned by separation principles that ensure boundary points can be approached from the interior without leaving the set.^[5] Another profound application is the proof of Farkas' lemma, a cornerstone of linear programming and feasibility analysis. The lemma states that for a matrix A \in \mathbb{R}^{m \times n} and vector b \in \mathbb{R}^m, the system Ax = b, x \geq 0 has a solution if and only if there exists no y \in \mathbb{R}^m such that A^T y \geq 0 and b^T y < 0. To prove this via separation, assume the system is infeasible, so b lies outside the convex cone generated by the columns of A, denoted \operatorname{cone}\{a_1, \dots, a_n\}, which is closed and convex. By the strict separating hyperplane theorem, there exists a nonzero y such that y^T z \leq 0 for all z \in \operatorname{cone}\{a_1, \dots, a_n\} (implying A^T y \leq 0) and y^T b > 0. Negating y yields the alternative form with A^T (-y) \geq 0 and b^T (-y) < 0. The converse follows by contradiction, as a feasible x would violate the inequality. Separation theorems also yield alternative characterizations of convexity. A closed set C is convex if and only if it equals the intersection of all closed half-spaces containing it. This follows directly from the supporting hyperplane theorem: for any point outside C, a strictly separating hyperplane exists, and C lies entirely on one side. Conversely, if C is the intersection of such half-spaces, it is convex as an intersection of convex sets. Equivalently, in terms of line segments, C is convex if no line segment joining two points in C intersects the complement of C in its relative interior; otherwise, separation would fail for points on opposite sides of the boundary. This geometric view underscores how improper crossing of the complement—meaning interior points outside C—violates the half-space representation.^[5] Finally, separation bridges to duality in optimization by implying weak duality for convex programs. Consider a convex minimization problem \inf \{ f(x) \mid x \in C \}, where f is convex and C is closed convex. If the infimum is not attained or constraints are inconsistent, separation between the epigraph of f and C yields a hyperplane whose normal provides a supporting functional, ensuring the primal value is at least the dual value. This establishes that feasible primal and dual objectives satisfy \sup g(y) \leq \inf f(x), where g is the dual function, without requiring strong duality.

Helly's Theorem and Selection Principles

Statement and Finite-Dimensional Case

Helly's theorem provides a fundamental condition for the nonempty intersection of a finite family of convex sets in Euclidean space. Specifically, let \{C_1, \dots, C_k\} be a finite collection of convex sets in \mathbb{R}^n with k \geq n+1. If the intersection of every n+1 of these sets is nonempty, then the intersection of all k sets is nonempty.^[25] This result establishes that the Helly number for the family of convex sets in \mathbb{R}^n is n+1, meaning n+1 is the smallest integer such that the intersection property for subfamilies of that size guarantees a common intersection for the entire family.^[26] The proof of Helly's theorem in finite dimensions proceeds by induction on the number of sets k. The base case k = n+1 holds by the hypothesis that every n+1 sets intersect. For the inductive step, assume the theorem holds for all families with fewer than k sets, where k > n+1. For each i = 1, \dots, k, consider the subfamily \{C_j : j \neq i\}, which has k-1 < k sets. Every n+1 sets in this subfamily intersect, so by the inductive hypothesis, \bigcap_{j \neq i} C_j \neq \emptyset; select a point a_i \in \bigcap_{j \neq i} C_j. The points \{a_1, \dots, a_k\} \subset \mathbb{R}^n with k \geq n+2 now satisfy the conditions of Radon's theorem, which states that any finite set of at least n+2 points in \mathbb{R}^n can be partitioned into two disjoint subsets I and J such that \operatorname{conv}(\{a_i : i \in I\}) \cap \operatorname{conv}(\{a_j : j \in J\}) \neq \emptyset.^[25] Let y be a point in this nonempty intersection. For any fixed \ell \in \{1, \dots, k\}, if \ell \in I, then each a_i for i \in I (with i \neq \ell) belongs to C_\ell, and since C_\ell is convex, y \in C_\ell; the case \ell \in J is symmetric. Thus, y \in \bigcap_{\ell=1}^k C_\ell, completing the induction.^[26] A representative example illustrates the theorem in low dimensions. In \mathbb{R}^2 (where n=2), the Helly number is 3: if every collection of 3 convex sets from a finite family has nonempty intersection, then the entire family intersects. For instance, consider 4 convex sets in the plane such that every trio shares a common point; Helly's theorem guarantees a point common to all four, even if pairwise intersections alone do not suffice.^[26] A dual form of Helly's theorem concerns piercing numbers for families of convex sets. If every subfamily of at most n+1 convex sets in \mathbb{R}^n can be pierced by a single point (i.e., has piercing number 1), then the entire finite family has piercing number 1.^[27] This duality highlights the symmetry between intersection properties and transversal (piercing) properties in convex geometry.^[28]

Infinite-Dimensional Extensions

In locally convex Hausdorff topological vector spaces, Helly's theorem extends to infinite families of closed convex sets via the finite intersection property: if every finite subcollection has non-empty intersection and each set is compact, then the total intersection is non-empty. This generalizes the finite-dimensional case, where the Helly number is finite, by requiring the stronger condition that all finite subfamilies intersect, reflecting the absence of a finite Helly number in infinite dimensions. The result holds because compact convex sets in such spaces are metrizable and the topology ensures the necessary closedness properties. The proof relies on Tychonoff's theorem applied to the product space of the sets. Consider the product P = \prod_{i \in I} C_i, which is compact in the product topology since each C_i is compact. The desired intersection corresponds to the non-emptiness of the diagonal subset D = \{ (x_i)_{i \in I} \in P \mid x_i = x_j \ \forall i,j \}. This diagonal is the intersection of the closed subsets D_{ij} = \{ (x_k) \in P \mid x_i = x_j \} for all pairs i,j \in I. The family \{ D_{ij} \} has the finite intersection property because any finite collection of such subsets involves only finitely many indices, and the finite intersection property of the C_i ensures a common point for those coordinates, extendable to the rest of the product. Since P is compact and the D_{ij} are closed, their intersection D is non-empty, yielding a point in \bigcap C_i. Variants adapt this to Banach spaces by replacing norm compactness with weak compactness. In a Banach space, if the sets are weakly closed and weakly compact (e.g., in reflexive spaces where closed bounded convex sets are weakly compact by Eberlein–Šmulian theorem), and possess the finite intersection property in the weak topology, the total weak intersection is non-empty via a similar product argument in the weak topology, as Tychonoff's theorem applies to the product of weakly compact sets. Total boundedness can also suffice in complete metric locally convex spaces, ensuring compactness under the metric. These extensions leverage the weak topology's utility for convex sets, where extreme points and supporting hyperplanes behave analogously to the strong topology. Without compactness or suitable topological assumptions, the finite intersection property fails to guarantee non-empty total intersection, even for closed convex sets. A counterexample in the Hilbert space \ell^2 is the family \{ C_n \mid n \in \mathbb{N} \} where C_n = \{ x \in \ell^2 \mid \langle x, e_n \rangle \geq 1 \} and \{e_n\} is the standard orthonormal basis; every finite subcollection intersects non-emptily (solving the finite system of inequalities yields a point in \ell^2), but the total intersection is empty since any x would satisfy \sum | \langle x, e_n \rangle |^2 = \infty, contradicting x \in \ell^2. In purely algebraic infinite-dimensional vector spaces without topology, similar constructions show that the finite intersection property alone does not suffice, as there are no compactness mechanisms to force consistency across infinitely many constraints, such as projections onto infinite bases leading to inconsistencies. The Hilbert cube example highlights further issues: the infinite product [0,1]^\mathbb{N} embedded in \ell^2 is compact in the product topology but not norm-compact, and families exploiting this mismatch can violate intersection guarantees under norm topology.

Combinatorial Implications

Helly's theorem plays a pivotal role in combinatorial geometry by providing bounds on the intersection properties of families of convex sets, with direct applications to discrete structures such as polytopes. The Helly number of a family of sets is the smallest integer h such that if every subfamily of at most h sets has nonempty intersection, then the entire family does. For the family of all convex polytopes in \mathbb{R}^d, the Helly number is d+1, mirroring the bound for general convex sets and enabling efficient algorithmic checks for common transversals or intersections in polyhedral arrangements.^[29] This combinatorial bound is sharp, as demonstrated by configurations of d+1 polytopes where every d intersect but the full collection does not, such as simplices positioned at the vertices of a larger simplex.^[30] In the realm of intersection theorems, Helly's theorem implies structural results akin to the Erdős–Ko–Rado theorem for intersecting families of convex sets. Specifically, for families of convex sets in \mathbb{R}^d that are pairwise intersecting, Helly's theorem ensures that under additional conditions (such as bounded dimension), the family admits a common point if every d+1 subsets intersect, leading to extremal bounds on the size of such families analogous to the Erdős–Ko–Rado bound \binom{n-1}{k-1} for k-uniform set families. This connection extends to hypergraph settings, where the Helly property—pairwise edges implying a common vertex—characterizes colorings and uniform hypergraphs with bounded intersection numbers, facilitating proofs of non-trivial intersecting families in geometric hypergraphs.^[31] The fractional Helly theorem offers a probabilistic relaxation, quantifying approximate intersections for large families. For a finite family \mathcal{F} of convex sets in \mathbb{R}^d, if the fraction of (d+1)-tuples with nonempty intersection exceeds $1 - (1 - \beta)^{d+1}, then there exists a subfamily of size at least \beta |\mathcal{F}| with nonempty common intersection.^[29] This result, established by Kalai, holds for the strong fractional Helly property with index d+1 and has implications for randomized algorithms in computational geometry, such as approximate piercing of set systems.^[32] In discrete settings, such as integer points within convex sets, Bárány and Matoušek extended this to guarantee a positive fraction \alpha(d) of the family sharing a common integer point when every d+1 do.^[32] Higher-order variants of Helly's theorem address multi-wise intersections, implying total intersection from controlled partial overlaps. For instance, if every subfamily of size at most \psi(k,d) = \max(d+1, 2(d - k + 1)) has intersection of dimension at least k, then the entire family in \mathbb{R}^d has intersection dimension at least k.^[29] These theorems, due to Katona, underpin results in topological combinatorics, such as the existence of high-dimensional common transversals in families with k-wise intersection guarantees, and connect to hypergraph Turán problems by bounding the size of k-uniform hypergraphs with restricted intersection patterns.^[32] Illustrative examples arise from families of unit balls in \ell_p norms, where Helly's theorem sharpens understanding of intersection patterns. In \mathbb{R}^d with the \ell_p norm ($1 \leq p \leq \infty), the unit balls are convex, so the Helly number remains d+1; however, for p=1 or p=\infty, the octahedral or cubic shapes allow explicit constructions showing sharpness, such as d+1 translated unit balls where every d intersect at a point but the full set misses it, highlighting combinatorial tightness in normed spaces.^[30] For disjoint unit balls, quantitative extensions yield Helly-type bounds for line transversals, with any $4d-1 admitting one implying the whole family does.^[29]

Convex Polytopes

Definitions and Facets

A convex polytope in Euclidean space \mathbb{R}^d is defined as the convex hull of a finite set of points, ensuring the set is compact and bounded.^[33] Equivalently, it can be expressed as the intersection of a finite number of closed half-spaces, where the intersection is bounded. This dual representation highlights the vertex-based and facet-based descriptions of polytopes, central to their study in convex geometry. The facial structure of a convex polytope P arises from its intersections with supporting hyperplanes. A supporting hyperplane H to P is a hyperplane such that H \cap P \neq \emptyset and P lies entirely in one of the closed half-spaces bounded by H. The faces of P are the nonempty sets F = P \cap H for such supporting hyperplanes H, including faces of dimensions from 0 up to \dim P - 1.^[33] Proper faces exclude P itself and the empty set. Among these, vertices are the 0-dimensional faces, edges are the 1-dimensional faces connecting vertices, and facets are the codimension-1 faces, which form the "sides" of the polytope.^[33] The dimension of a convex polytope P is the dimension of its affine hull, the smallest affine subspace containing P. Every face F of P inherits this structure, with its relative interior consisting of points in F that are interior relative to the affine hull of F. The boundary of P is the union of all its proper faces, while the relative interior of P forms its "inside." This decomposition into relative interior and boundary facilitates analysis of the polytope's geometry and topology. Representative examples illustrate these concepts. The standard n-simplex in \mathbb{R}^n is the convex hull of n+1 affinely independent points, such as the origin and the standard basis vectors, possessing n+1 vertices and n+1 facets.^[34] The n-cube, or hypercube, is the convex hull of the $2^n points with coordinates (\pm 1, \dots, \pm 1), featuring $2^n vertices, $2nfacets (each an(n-1)-cube), and a highly symmetric facial structure. The n-dimensional cross-polytope, dual to the n

-cube, is the convex hull of the &#36;2n

points \pm e_i (where e_i are standard basis vectors), with $2nvertices and2^n$ triangular facets, exemplifying self-duality in even dimensions.^[35]

Euler's Formula

Euler's formula, also known as the Euler-Poincaré relation in higher dimensions, provides a fundamental relation among the face numbers of a convex polytope. For a three-dimensional convex polytope, or polyhedron, if V denotes the number of vertices, E the number of edges, and F the number of faces (including the bounding 2-faces but excluding the interior), the formula states that V - E + F = 2.^[36] This relation holds for any convex polyhedron homeomorphic to a sphere and reflects its topological invariance.^[37] A classic example is the tetrahedron, the simplest convex polyhedron, which has V = 4 vertices, E = 6 edges, and F = 4 faces, satisfying $4 - 6 + 4 = 2.^[36] This verifies the formula directly and illustrates how it balances the combinatorial structure of the polytope. In general, for a d-dimensional convex polytope P, let f_k(P) denote the number of k-dimensional faces for k = 0, 1, \dots, d, where f_0 = V, f_1 = E, f_d = 1 (the polytope itself), and higher f_k count the intermediate faces. The Euler-Poincaré formula asserts that

\sum_{k=0}^d (-1)^k f_k(P) = 1.

^[37] For the three-dimensional case, this reduces to f_0 - f_1 + f_2 - f_3 = 1, or equivalently V - E + F = 2 since f_3 = 1. In some conventions, including the empty face as f_{-1} = 1, the alternating sum from k = -1 to d equals 0, emphasizing the topological Euler characteristic of the polytope as a ball.^[38] A proof of the formula can be sketched using shelling, a combinatorial decomposition technique showing that every convex polytope is shellable.^[38] Proceed by induction on the dimension d and the number of facets. A shelling orders the d-faces F_1, \dots, F_m (with m = f_{d-1}) such that each F_j intersects the previous union in a pure (d-1)-dimensional initial segment of its own shelling. The Euler characteristic \chi is additive: \chi(K_1 \cup K_2) = \chi(K_1) + \chi(K_2) - \chi(K_1 \cap K_2). Starting with \chi(F_1) = 1 (a simplex has alternating sum 1), each addition of F_j increases the complex while preserving the characteristic via the intersection properties, yielding \chi(P) = 1 at the end.^[38] The formula implies useful bounds on the combinatorial size of polytopes. For a three-dimensional convex polytope, assuming each face has at least three edges and each edge bounds two faces, double counting gives $2E \geq 3F. Substituting into Euler's formula yields F \leq \frac{2E}{3}, so V = E - F + 2 \geq E - \frac{2E}{3} + 2 = \frac{E}{3} + 2, or equivalently E \leq 3V - 6 for V \geq 3.^[39] This bound, derived from the polytope's graph planarity, limits the edge complexity relative to vertices and extends to analogous inequalities in higher dimensions via the full f-vector relations.^[40]

Schläfli Symbol

The Schläfli symbol is a concise notation for classifying regular polytopes, which are convex polytopes where all faces, edges, and vertices are congruent and symmetrically arranged. Introduced by the Swiss mathematician Ludwig Schläfli in his seminal 1852 work Theorie der vielfachen Kontinuität, the symbol takes the form \{p, q, \dots, r\}, where each integer parameter recursively encodes the local structure of the polytope's cells and their incidences.^[41]^[42] In three dimensions, the symbol simplifies to \{p, q\} for a regular polyhedron, with p specifying the number of sides of each regular polygonal face (a p-gon) and q denoting the number of faces meeting at each vertex. This recursive definition extends naturally to higher dimensions: for a four-dimensional regular polytope \{p, q, r\}, the three-dimensional cells are \{p, q\} polyhedra, and exactly r such cells meet at each edge. In general, the sequence describes the dimension-by-dimension composition, with the final entry indicating the vertex figure's structure.^[41] Illustrative examples abound among the classical regular polytopes. The cube has Schläfli symbol \{4, 3\}, reflecting its square (p=4) faces with three meeting at each vertex (q=3); the regular dodecahedron is \{5, 3\}, with pentagonal faces and three per vertex. Extending to four dimensions, the 4-simplex (or pentachoron) is denoted \{3, 3, 3\}, consisting of eight tetrahedral (\{3, 3\}) cells, three of which meet at each edge. These symbols capture the essential symmetry of the Platonic solids and their higher-dimensional analogs.^[41] A key property of the Schläfli symbol is that it fully determines the combinatorial type of a regular polytope, specifying the complete incidence relations among its vertices, edges, faces, and higher cells. This exhaustive description enables computations of global features, such as the number of elements in each dimension, and aligns with topological constraints like Euler's formula in finite dimensions for verification. For uniform polytopes, which maintain vertex-transitivity but allow varied face types, the symbol provides a foundational encoding, though adaptations are needed for non-regular cases.^[41] The notation is inherently limited to regular polytopes, where all facets and vertex figures are identical regular polytopes themselves; it does not directly apply to irregular or non-convex forms. Extensions to semi-regular (Archimedean) polytopes and star polyhedra employ related constructs, such as Wythoff symbols, which incorporate reflection groups to generate more diverse uniform figures.^[41]

Convex Bodies

Mixed Volumes

Mixed volumes are fundamental objects in the Brunn–Minkowski theory of convex geometry, providing a multilinear extension of the volume functional to tuples of convex bodies in Euclidean space. For convex bodies K_1, \dots, K_d \in \mathcal{K}^d in \mathbb{R}^d, where \mathcal{K}^d denotes the set of compact convex subsets with nonempty interior, the mixed volume V(K_1, \dots, K_d) is defined as the coefficient in the homogeneous polynomial expansion of the volume of their Minkowski linear combination. Specifically, for nonnegative scalars \lambda_1, \dots, \lambda_m \geq 0 and convex bodies K_1, \dots, K_m \in \mathcal{K}^d,

V\left( \sum_{i=1}^m \lambda_i K_i \right) = \sum_{i_1=1}^m \cdots \sum_{i_d=1}^m \lambda_{i_1} \cdots \lambda_{i_d} \, V(K_{i_1}, \dots, K_{i_d}),

where the mixed volume on the right is extended by multilinearity to allow repetitions, often denoted V(K_1[j_1], \dots, K_m[j_m]) with j_1 + \dots + j_m = d and j_k indicating the number of times K_k appears.^[43] This expansion originates from the observation that the volume functional is homogeneous of degree d, leading to a polynomial structure under Minkowski addition. The concept was introduced by Hermann Minkowski in his foundational work on volumes and surfaces of convex bodies, where he established the algebraic framework for these coefficients.^[43] Mixed volumes possess several key properties that underscore their role as a natural generalization of volume. They are symmetric in their arguments, meaning V(K_{\pi(1)}, \dots, K_{\pi(d)}) = V(K_1, \dots, K_d) for any permutation \pi of \{1, \dots, d\}, and multilinear, so that for \alpha, \beta \geq 0 and convex bodies L, M \in \mathcal{K}^d,

V(\alpha L + \beta M, K_2, \dots, K_d) = \alpha V(L, K_2, \dots, K_d) + \beta V(M, K_2, \dots, K_d).

Moreover, when all arguments are identical, the mixed volume recovers the ordinary volume: V(K, \dots, K) = V(K), where V(K) denotes the d-dimensional Lebesgue measure of K. These properties ensure that mixed volumes form a complete basis for the space of homogeneous degree-d polynomials on the coefficients in the Minkowski sum expansion.^[43] A prominent example of mixed volumes arises in the expression for intrinsic volumes and quermassintegrals of a convex body K \in \mathcal{K}^d. In particular, the surface area S(K) of K is given by

S(K) = d \, V(K[d-1], B{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}})

, where B is the unit ball in \mathbb{R}^d and K indicates K repeated j times. This relation follows from the Steiner formula for the volume of the parallel body K + \varepsilon B, whose linear term in \varepsilon yields the surface area as the mixed volume involving one copy of the ball and d-1 copies of K. More generally, the quermassintegrals W_j(K), which interpolate between volume and mean width, are proportional to V(K[d-j], B). These examples illustrate how mixed volumes encode geometric information beyond mere volume, such as perimeter in the plane (d=2) or surface functionals in higher dimensions.^[43]

Brunn-Minkowski Inequality

The Brunn–Minkowski inequality is a cornerstone of convex geometry, asserting that for nonempty compact convex bodies K and L in Euclidean space \mathbb{R}^d, the d-th root of the volume of their Minkowski sum satisfies

[\operatorname{vol}(K + L)]^{1/d} \geq [\operatorname{vol}(K)]^{1/d} + [\operatorname{vol}(L)]^{1/d},

where \operatorname{vol} denotes the d-dimensional Lebesgue measure.^[44] This inequality captures the superadditivity of volumes under Minkowski addition and extends the classical Brunn principle from 1887 to general convex sets, as fully established by Minkowski in 1896.^[44] A standard proof proceeds through the theory of mixed volumes, where the volume of the Minkowski sum K + tL for t \geq 0 is expressed as a homogeneous polynomial of degree d: \operatorname{vol}(K + tL) = \sum_{k=0}^d \binom{d}{k} V(K[d-k], L) t^k, with V(\cdot) denoting mixed volumes.^[45] The first mixed volume V(K[d-1], L) governs the surface area behavior, and the concavity of the function f(t) = [\operatorname{vol}(K + tL)]^{1/d} follows from the nonnegativity and subadditivity properties of mixed volumes, yielding f(1) \geq f(0) + f(1) - f(0) at t=1.^[44] An alternative proof leverages the Prékopa–Leindler functional inequality, which states that for nonnegative measurable functions f, g, h on \mathbb{R}^d satisfying h((1-\lambda)x + \lambda y) \geq f(x)^{1-\lambda} g(y)^\lambda for $0 < \lambda < 1 and all x, y \in \mathbb{R}^d, the integrals obey \int h \geq \left( \int f \right)^{1-\lambda} \left( \int g \right)^\lambda.^[46] Applying this to the characteristic functions of K and L recovers the geometric inequality via the concavity of the logarithm.^[45] Equality holds in the Brunn–Minkowski inequality if and only if K and L are homothetic, meaning there exists a vector c \in \mathbb{R}^d and \alpha \geq 0 such that L = \alpha K + c.^[44] This condition arises from the strict concavity in the mixed volume expansion unless the bodies share the same supporting hyperplanes up to scaling and translation, as analyzed in the original proofs.^[47] The inequality extends naturally to measures beyond Lebesgue volume, particularly for log-concave densities. For a log-concave Borel probability measure \mu on \mathbb{R}^d (i.e., d\mu/d\lambda = e^{-\psi} where \psi is convex) and compact sets K, L \subseteq \mathbb{R}^d, [\mu((1-\lambda)K + \lambda L)]^{1/d} \geq (1-\lambda) [\mu(K)]^{1/d} + \lambda [\mu(L)]^{1/d} for $0 \leq \lambda \leq 1. This follows from the concavity of the function \lambda \mapsto [\mu((1-\lambda)K + \lambda L)]^{1/d} for log-concave measures.^[46] Such extensions underpin applications in functional analysis and probability, including Gaussian measures in infinite-dimensional spaces.^[47]

Isoperimetric Problems

In convex geometry, isoperimetric problems seek to quantify the optimal trade-offs between the volume and surface area of convex bodies, revealing how closely a given body approximates a ball in terms of these measures. For a convex body K in \mathbb{R}^d, the classical isoperimetric inequality provides a lower bound on the surface area S(K) relative to the volume V(K), stating that

S(K)^d \geq d^d \kappa_d V(K)^{d-1},

where \kappa_d is the volume of the unit ball in \mathbb{R}^d, with equality if and only if K is a ball.^[44] This inequality, originally inspired by Steiner's work on parallel curves and surfaces, extends the two-dimensional case where the perimeter squared is at least $4\pi times the area, and it holds for all compact convex sets due to their regularity properties.^[44] A related refinement is Urysohn's inequality, which connects the volume of K to its mean width w(K), defined as the average width over all directions:

\left( \frac{V(K)}{\kappa_d} \right)^{1/d} \leq \frac{w(K)}{w(B)},

where B is the unit ball and w(B) = 2, with equality again for the ball.^[48] This inequality underscores that among convex bodies of fixed volume, the ball minimizes the mean width, providing an isoperimetric-type bound on directional extents. Proofs often leverage the Brunn-Minkowski inequality to establish monotonicity in symmetrization processes.^[48] The Löwner-John ellipsoid exemplifies these principles by identifying, for any convex body K in \mathbb{R}^d, a unique ellipsoid of minimal volume containing K (the Löwner ellipsoid) or maximal volume inscribed in K (the John ellipsoid), satisfying E \subseteq K \subseteq d \cdot E after affine transformation, where d is the dimension.^[49] This ellipsoid achieves the extremal position, bounding the volume ratio between K and its "most ellipsoidal" approximation, which directly informs isoperimetric deficits by measuring deviation from the equality case of the ball.^[49] These inequalities connect to the Steiner formula, which describes the volume of the parallel body K_r = K + r B as

V(K_r) = \sum_{k=0}^d \binom{d}{k} W_k(K) r^k,

where the quermassintegrals W_k(K) encode intrinsic volumes, with W_0(K) = V(K), W_1(K) proportional to the mean width, and W_{d-1}(K) related to the surface area.^[50] The coefficients in this polynomial expansion facilitate derivations of isoperimetric bounds, as the linear term in r involves surface area and higher terms reflect curvature-like properties, linking perimeter-volume relations to expansions around the body.^[50]

Duality in Convex Geometry

Polar and Dual Cones

In convex geometry, the polar of a convex set K \subseteq \mathbb{R}^n containing the origin is defined as the set

K^\circ = \{ y \in \mathbb{R}^n \mid \langle x, y \rangle \leq 1 \ \forall x \in K \}.

This construction provides a duality that maps convex sets to other convex sets, with K^\circ always being closed, convex, and containing the origin.^[51] The polar operation reverses inclusions: if K \subseteq L, then L^\circ \subseteq K^\circ.^[51] For convex cones, a related but distinct dual construction is used. The dual cone K^* of a cone K \subseteq \mathbb{R}^n (not necessarily containing the origin in the same way) is

K^* = \{ y \in \mathbb{R}^n \mid \langle x, y \rangle \geq 0 \ \forall x \in K \}.

Unlike the polar, the dual cone always contains the origin and is closed and convex, even if K is neither.^[52] The dual cone captures the directions "orthogonal" in a nonnegative sense to K, and it satisfies containment reversal: if K \subseteq L, then L^* \subseteq K^*.^[53] A fundamental result linking these dualities is the bipolar theorem, which states that for a closed convex set K \subseteq \mathbb{R}^n containing the origin, K = (K^\circ)^*, where the outer dual is taken with respect to the polar form. More generally, the bidual satisfies (K^\circ)^* = \overline{\operatorname{conv}}(K \cup \{0\}), recovering the closed convex hull of K adjoined with the origin. This theorem, proved using separation properties of hyperplanes, establishes the polar and dual operations as inverses under closure and convexity assumptions. Geometrically, the bipolar theorem implies that points outside K can be separated from K by a hyperplane whose normal lies in the polar.^[54] A classic example arises with unit balls in \ell_p-norms. The polar of the unit ball B_p = \{ x \in \mathbb{R}^n \mid \|x\|_p \leq 1 \} (for $1 \leq p \leq \infty) is the unit ball B_q = \{ y \in \mathbb{R}^n \mid \|y\|_q \leq 1 \}, where q is the conjugate exponent satisfying \frac{1}{p} + \frac{1}{q} = 1.^[55] This duality highlights how the \ell_p-ball and its polar \ell_q-ball are norm duals, with the case p=2 yielding self-duality for the Euclidean ball.^[55]

Santaló Point

In convex geometry, the Santaló point of a convex body K \subset \mathbb{R}^n with non-empty interior is defined as the unique point s(K) \in \operatorname{int} K that minimizes the product of the volumes \operatorname{vol}_n(K - c) \cdot \operatorname{vol}_n((K - c)^\circ) over all c \in \mathbb{R}^n, where (K - c)^\circ denotes the polar body of the translated set K - c with respect to the origin. This minimization defines an affine-invariant functional on convex bodies, originally introduced to study geometric inequalities involving duality. The existence and uniqueness of the Santaló point follow from the strict concavity of the logarithm of the volume product functional, ensuring a unique minimizer for any full-dimensional convex body. For convex bodies centered at their centroid (i.e., with barycenter at the origin), the Santaló point provides a canonical reference for polarity and volume comparisons.^[56] In particular, for ellipsoids, the Santaló point coincides with the geometric center, reflecting their affine regularity under polarity.^[57] The Santaló point plays a central role in the Mahler conjecture, which posits that the minimal value of the volume product \operatorname{vol}_n(K) \cdot \operatorname{vol}_n(K^\circ) over all origin-symmetric convex bodies K (with Santaló point at the origin) is \frac{4^n}{(n!)^2}, achieved by the hypercube and its polar, the cross-polytope.^[58] For non-symmetric convex bodies, the conjecture asserts a lower bound of \frac{(n+1)^{n+1}}{(n!)^2}, with equality for simplices.^[59] This conjecture connects the Santaló point to extremal problems in asymptotic convex geometry, with partial resolutions in low dimensions and for specific classes. For the Euclidean unit ball B_2^n, the Santaló point is the origin, yielding the maximal volume product \operatorname{vol}_n(B_2^n)^2 = (\pi^{n/2}/\Gamma(n/2 + 1))^2 among all convex bodies by the Blaschke-Santaló inequality.^[60] In the case of unconditional convex bodies (symmetric with respect to all coordinate hyperplanes and containing the origin in their interior), the origin serves as the Santaló point, simplifying applications of duality to coordinate-based estimates and reverse inequalities.^[61]

Applications to Optimization

Convex geometry provides foundational tools for optimization through the duality between convex sets and their polars, enabling the formulation of dual problems that bound primal objectives and ensure optimality under certain conditions. In convex programming, this manifests as Lagrange duality, where the primal problem of minimizing a convex function subject to convex inequality constraints is paired with a dual maximization problem over non-negative multipliers. Specifically, consider the primal problem: minimize f(x) subject to g_i(x) \leq 0 for i = 1, \dots, m, where f and each g_i are convex functions defined on a convex set. The Lagrangian is L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x), and the dual function is d(\lambda) = \inf_x L(x, \lambda) for \lambda \geq 0. The dual problem then maximizes d(\lambda) over \lambda \geq 0. Weak duality holds universally for convex problems, stating that the primal optimal value is at least the dual optimal value, due to the minimax theorem applied to convex-concave Lagrangians over convex sets. Strong duality, where the primal and dual optimal values coincide, requires qualification conditions rooted in the separation properties of convex sets. Slater's condition ensures this zero duality gap: if there exists a strictly feasible point x in the relative interior of the domain such that g_i(x) < 0 for all non-affine g_i, then strong duality obtains. This leverages the interior-point theorem in convex geometry, which guarantees hyperplane separation between a point and a convex set without interior points, implying no duality gap when the primal feasible set has nonempty relative interior. Without such conditions, duality gaps may arise, but in convex settings, they highlight the geometric constraints' role in optimization feasibility.^[62] The Karush-Kuhn-Tucker (KKT) conditions characterize optimality in convex programs under constraint qualifications like Slater's, extending Lagrange multipliers to inequalities via subgradients for nondifferentiable convex functions. For a convex primal problem, a point x^* is optimal if there exist \lambda^* \geq 0 such that stationarity holds: $0 \in \partial f(x^*) + \sum_i \lambda_i^* \partial g_i(x^*); primal feasibility: g_i(x^*) \leq 0; dual feasibility: \lambda^* \geq 0; and complementary slackness: \lambda_i^* g_i(x^*) = 0 for all i. These conditions are necessary and sufficient for convexity, as they encode the zero-subgradient property at the optimum, tied to supporting hyperplanes in the epigraph of the objective over the feasible set. Subgradients here represent the convex set's tangent approximations, ensuring the conditions align with geometric duality.^[63] A prominent example is linear programming, where the objective and constraints are linear, rendering the feasible set a polyhedron—a bounded convex body. The primal minimizes c^\top x subject to Ax \leq b, x \geq 0, with dual maximizing b^\top y subject to A^\top y \leq c, y \geq 0. Polyhedral sets satisfy Slater's condition if the relative interior is nonempty, yielding strong duality and KKT conditions that reduce to complementary slackness and basic feasible solutions, underpinning efficient solvers while illustrating convex duality's role in bounding linear objectives over intersection of half-spaces.

History

Early Developments

The origins of convex geometry trace back to ancient antiquity, where foundational ideas emerged in the study of volumes and surfaces of simple convex shapes. Around 250 BC, Archimedes, in his treatise On the Sphere and Cylinder, demonstrated that the surface area of a sphere equals that of its circumscribing cylinder (excluding the bases) and that the sphere's volume is two-thirds that of the enclosing cylinder, providing early insights into isoperimetric relations among convex bodies. These results, derived through mechanical and geometric methods, highlighted comparative properties of convex solids that would later inform broader convexity principles.^[64] Advancements in the 18th and 19th centuries shifted focus toward systematic properties of polyhedra and curves, building intuitive geometric foundations. In 1752, Leonhard Euler established his famous polyhedral formula, stating that for any convex polyhedron, the number of vertices V minus the number of edges E plus the number of faces F equals 2 (V - E + F = 2), a relation that underscored topological invariants in convex polytopes.^[65] This formula, initially motivated by enumerative problems, provided an early tool for classifying convex polyhedral structures. By 1845, Augustin-Louis Cauchy advanced integral geometry with the Cauchy-Crofton formula, which expresses the length of a rectifiable curve as a quarter of the integral measure of lines intersecting it in the plane, offering a probabilistic means to quantify boundaries of convex domains.^[66] The late 19th century marked a pivotal transition to abstract convex body theory, largely through Hermann Minkowski's seminal contributions. In his 1896 monograph Geometrie der Zahlen, Minkowski formalized the study of convex bodies—compact sets closed under convex combinations—as central objects, developing their volume properties in the context of lattice point enumeration.^[67] In his 1897 paper "Allgemeine Lehrsätze über die konvexen Polyeder", Minkowski introduced mixed volumes, which generalize scalar volumes to multilinear functionals on multiple convex bodies, enabling precise analysis of Minkowski sums and enabling applications in number theory.^[68] In the same work, Minkowski provided a rigorous proof of the Brunn-Minkowski inequality, asserting that for nonempty compact convex sets K, L \subset \mathbb{R}^n with positive volume, the volume of their Minkowski sum satisfies |K + L|^{1/n} \geq |K|^{1/n} + |L|^{1/n}, with equality if and only if K and L are homothetic; this inequality, building on Hermann Brunn's earlier conjecture, established a foundational link between convexity and volume additivity.^[2]

Modern Foundations

The modern foundations of convex geometry emerged in the early 20th century through axiomatization efforts that integrated classical geometric insights with principles from functional analysis. A pivotal early contribution was Eduard Helly's 1912 proof of a special case of Helly's theorem, applicable to families of closed intervals on the real line, where the intersection condition ensures a common point for the entire collection.^[69] This laid groundwork for broader intersection properties of convex structures. Helly extended the result in 1923 to general convex sets in Euclidean space, establishing that if every subcollection of at most d+1 sets from a family of convex sets in ℝ^d has nonempty intersection, then the whole family does.^[70] In the 1930s, the Hahn-Banach theorem marked a significant advancement by providing tools for separating convex sets from exterior points via hyperplanes, thus formalizing duality and extension principles central to convex geometry's axiomatic structure.^[71] Originally anticipated in Helly's 1912 work on linear functionals, the theorem was independently proved by Hans Hahn in 1927 and Stefan Banach in 1932, enabling rigorous treatments of convex sets within normed spaces.^[71] These separation theorems became foundational, underpinning subsequent developments in the field. The Krein-Milman theorem of 1940 further solidified this framework by showing that every compact convex subset of a locally convex Hausdorff topological vector space equals the closed convex hull of its extreme points.^[72] Post-World War II research extended classical inequalities into more abstract settings, notably through generalizations of the Brunn-Minkowski inequality to functional and measure-theoretic contexts. The Prékopa-Leindler inequality, developed by András Prékopa in 1973 and József Leindler in 1972, provides a functional analogue, stating that for log-concave functions satisfying certain marginal conditions, the integral of their convex combination is at least the convex combination of their integrals.^[46] This extension facilitated applications to probability measures and optimization while preserving the inequality's geometric essence. The 1960s saw the inception of asymptotic convex geometry, emphasizing high-dimensional behaviors of convex bodies, with key refinements to Aryeh Dvoretzky's 1956 theorem on nearly Euclidean sections. Contributions from V.D. Milman and M. Gromov in this era and beyond highlighted concentration phenomena and metric properties, transforming convex geometry into a probabilistic and asymptotic discipline.^[73] A unifying milestone arrived with R. Tyrrell Rockafellar's 1970 monograph Convex Analysis, which systematically integrated convex sets with convex functions, subdifferentials, and conjugate duality, establishing a cohesive theory for nonlinear analysis.^[5]

Key Contributors

Hermann Minkowski (1864–1909) laid foundational stones in convex geometry through his work on lattice point problems and the introduction of mixed volumes. In his seminal 1896 monograph Geometrie der Zahlen, Minkowski established the geometry of numbers, proving that any convex body symmetric about the origin with volume greater than $2^n contains a non-zero lattice point, providing crucial bounds for integer solutions to inequalities.^[74] He introduced the concept of mixed volumes in his 1897 paper "Allgemeine Lehrsätze über die konvexen Polyeder" and further developed it in his 1903 paper "Volumen und Oberfläche", defining them as coefficients in the polynomial expansion of the volume of Minkowski sums of convex bodies, which enabled generalizations of classical inequalities and influenced subsequent theories in convex analysis.^[74] Ludwig Danzer (1927–2015) advanced combinatorial aspects of convex geometry, particularly through Helly-type theorems and universality results. Collaborating with Branko Grünbaum and Victor Klee, Danzer co-authored a comprehensive survey in 1963 that generalized Helly's theorem to families of convex sets, establishing bounds on intersection properties and their relatives in higher dimensions, which remain central to discrete geometry.^[69] His work on universality, including explorations of universal transversal systems for convex sets in the 1970s, demonstrated that certain finite configurations can intersect every member of a wide class of convex bodies, impacting tiling and packing problems.^[75] Victor Klee (1925–2007) made enduring contributions to polytope theory and its connections to optimization. In a 1967 paper with David Gale and R. Tyrrell Rockafellar, Klee analyzed convex functions on convex polytopes, showing that such functions attain minima at vertices and linking polyhedral combinatorics to linear programming, which bolstered the development of efficient optimization algorithms.^[76] As an editor of the influential 1963 volume Convex Polytopes (later revised in 2003 with Volker Kaibel and Günter M. Ziegler), Klee synthesized key results on polytope faces, diameters, and skeletons, fostering the field's growth in computational and infinite-dimensional settings.^[77] Keith Ball (born 1960) has shaped modern convex geometry with innovative inequalities and progress on the slicing problem. In his 1988 paper "Shadows of Convex Bodies," Ball proved that the average area of projections of a convex body onto k-dimensional subspaces is at least a constant times the k-th root of its volume, resolving cases of the Busemann-Petty problem and providing tools for asymptotic analysis.^[78] His 1997 survey "An Elementary Introduction to Modern Convex Geometry" elucidates connections between concentration phenomena and geometric inequalities, while his work on isotropic constants advanced the slicing conjecture by showing that every convex body admits a subspace of small isotropic constant, with implications for high-dimensional probability. Recent contributions to combinatorial convexity include those by women mathematicians such as Susanna Dann, who has explored sections and projections of convex bodies. In a 2016 collaboration with Silouanos Brazitikos, Apostolos Giannopoulos, and Alexander Koldobsky, Dann derived sharp estimates for the average volume of central sections of convex bodies, bridging geometric tomography and harmonic analysis with applications to L_p-norms.^[79] Her 2023 work on symmetries of convex bodies further examines how rotational and reflectional invariances affect surface area measures and centroid positions, enhancing understanding of isotropic properties in asymptotic convex geometry.^[80]

Applications

In Optimization

Convex geometry provides the foundational structure for linear programming (LP), where the feasible region defined by a system of linear inequalities and equalities is a bounded convex polytope, the intersection of half-spaces in Euclidean space.^[81] This polyhedral nature ensures that any local optimum is global, and for a linear objective function, the optimal value is attained at a vertex of the polytope.^[82] The simplex method, pioneered by George B. Dantzig in 1947, exploits this geometry by starting at a basic feasible solution corresponding to a vertex and iteratively pivoting along edges to adjacent vertices, each step improving the objective until an optimal vertex is reached.^[83] Although the method is highly efficient in practice for many problems, its worst-case time complexity can be exponential in the number of variables due to the potential abundance of vertices in high dimensions.^[84] The quest for a provably polynomial-time algorithm culminated in Leonid Khachiyan's 1979 ellipsoid method, which approximates the feasible polytope through a sequence of shrinking ellipsoids containing a point in the polytope, separating infeasible directions via oracles until feasibility or boundedness is resolved.^[85] This approach runs in time polynomial in the input size, establishing that LP is solvable in polynomial time and resolving a major open question in computational complexity.^[86] While theoretically significant, the ellipsoid method's practical performance is often inferior to the simplex method due to numerical instability and high constant factors. Interior-point methods, developed in the late 1980s and refined in subsequent decades, offer another polynomial-time framework deeply rooted in convex geometry, navigating the interior of the polytope along the central path—a curve of points that balance centrality with respect to the constraints and approximate the optimal solution.^[87] These methods rely on self-concordant barrier functions, which encode the geometry of the feasible set through a logarithmic barrier that prevents approaches to the boundary, ensuring smooth convergence properties independent of conditioning.^[87] The theoretical foundation, laid by Yurii Nesterov and Arkadi Nemirovski, shows that path-following algorithms using such barriers achieve polynomial iteration complexity, typically O(\sqrt{\nu} \log(1/\epsilon)) for accuracy \epsilon, where \nu is the barrier's complexity parameter.^[87] In practice, primal-dual variants of these methods have become the standard for large-scale LP solvers due to their superior empirical performance over both simplex and ellipsoid approaches. Convex geometry's influence extends to semidefinite programming (SDP), a generalization of LP where constraints involve linear matrix inequalities, and the feasible region is a spectrahedron—the feasible set of an SDP, formed as the projection of the intersection of the cone of positive semidefinite matrices with an affine subspace onto Euclidean space.^[88] Spectrahedra, introduced in the context of SDP optimization, are full-dimensional convex semialgebraic sets that generalize polytopes while preserving key facial structure properties, such as all faces being exposed, which aids in duality and algorithmic design.^[88] Optimization over spectrahedra employs interior-point methods analogous to those for LP, using the self-concordant barrier -\log \det(X) for the positive semidefinite cone, enabling polynomial-time solvability with complexity scaling favorably for moderate matrix sizes.^[87] This framework has broad applications in areas like control theory and combinatorial optimization, where SDP relaxations leverage the rich geometry of spectrahedra to provide tight approximations.^[88]

In Computational Geometry

In computational geometry, convex sets form the foundation for efficient algorithms that process point sets and shapes, enabling the solution of problems like proximity queries and spatial partitioning. A key primitive is the computation of the convex hull of a finite set of points in the plane, which identifies the smallest convex polygon enclosing all points. The Graham scan algorithm achieves this in O(n log n) time, where n is the number of points: it first selects the lowest y-coordinate point as the origin, sorts the remaining points by polar angle relative to this origin (taking O(n log n) time), and then iterates through the sorted list to construct the hull using a stack to eliminate non-convex turns.^[89] For cases where the output hull size h is small, the Jarvis march (also called the gift-wrapping algorithm) offers better performance at O(n h) time; it begins at an extreme point (e.g., the leftmost) and successively selects the next hull vertex by finding the point that forms the minimal polar angle with the current edge, simulating wrapping a string around the points.^[90] These algorithms are optimal in their respective regimes, with the logarithmic factor in Graham's scan arising from sorting, while Jarvis's efficiency shines when h << n, such as in sparse distributions. Voronoi diagrams and their duals, Delaunay triangulations, further exemplify convex geometry's role in partitioning space based on proximity. A Voronoi diagram divides the plane into cells where each cell consists of points closest to a given site under the Euclidean metric, with cell boundaries being perpendicular bisectors that are straight-line segments. The Delaunay triangulation, which connects sites whose Voronoi cells share an edge, forms a triangulation of the convex hull that maximizes the minimum angle among all possible triangulations, ensuring well-shaped triangles for mesh generation. Computationally, Delaunay triangulations can be derived by lifting the input points to the paraboloid z = x² + y² in three dimensions, where the lower faces of the resulting convex hull project back to the Delaunay edges in the plane; this reduction leverages 3D convex hull algorithms like the beneath-beyond method.^[91] The Minkowski sum of two convex sets A and B, defined as {a + b | a ∈ A, b ∈ B}, extends these ideas to shape combination, equivalent to convolving their indicator functions and yielding another convex set. For two convex polygons with n and m vertices, the sum is a convex polygon with at most n + m vertices, computable in O(n + m) time via a merging procedure: decompose each polygon into parallel edge chains sorted by outward normal direction, then advance along matching chains while adding offset vectors to form new edges. This linear-time method, akin to merging sorted lists, avoids explicit vertex enumeration of all n m sums by exploiting convexity. (Note: This 1999 paper by Ghosh discusses the algorithm in the context of optimization, but the core merge technique traces to earlier works like Preparata's 1985 text; for brevity, the complexity and approach are standard.) These structures underpin practical applications in computational settings. In computer graphics, convex hull approximations enable fast collision detection between objects by reducing intersection tests to separating hyperplane queries on hulls, accelerating rendering and simulation in real-time environments.^[92] In robot motion planning, Minkowski sums construct the configuration space obstacle (C-obstacle) by summing the robot's geometry with flipped obstacles, transforming pathfinding into navigation around convex regions to avoid collisions while respecting joint limits.^[93]

In Functional Analysis

In functional analysis, convex geometry plays a central role through the study of unit balls in Banach spaces, which are compact, convex, symmetric sets in finite dimensions and more general convex bodies in infinite dimensions. These unit balls encode the norm structure of the space, allowing geometric properties of convex sets to inform analytic properties like reflexivity and dimensionality. Key theorems bridge these areas by characterizing when a Banach space's geometry resembles that of familiar spaces such as Hilbert or \ell_p spaces. James' theorem provides a foundational link between the convexity of the unit ball and reflexivity in Banach spaces. Specifically, a Banach space X is reflexive if and only if every continuous linear functional on X attains its norm on the closed unit ball B_X. This norm attainment condition is equivalent to the weak compactness of B_X, since in non-reflexive spaces, there exist functionals that fail to achieve their supremum on B_X, implying the ball is not weakly compact. By the Krein-Milman theorem, the weak compactness of B_X ensures that the convex hull of its extreme points is weakly dense in B_X, highlighting the role of extreme points in the geometry of reflexive spaces. James constructed a counterexample, the James space J, which is quasi-reflexive (its codimension-one subspace is reflexive) but non-reflexive, demonstrating that the unit ball's geometry can fail weak compactness in subtle ways. Dvoretzky's theorem extends convex geometric insights to high-dimensional Banach spaces, revealing nearly Euclidean structure in subspaces. For any n-dimensional Banach space X and \varepsilon > 0, there exists a subspace of dimension at least c(\varepsilon) \log n that embeds into Euclidean space with distortion at most $1 + \varepsilon, where c(\varepsilon) > 0 is a constant depending only on \varepsilon. This result implies that high-dimensional convex bodies, as unit balls, contain almost round sections, approximating the Euclidean ball up to small distortion. In infinite-dimensional settings, every infinite-dimensional Banach space contains finite-dimensional subspaces arbitrarily close to Hilbertian in this sense, underscoring the ubiquity of Euclidean-like geometry within broader convex structures. The distortion problem in convex geometry is formalized via the Banach-Mazur distance, which quantifies how closely two symmetric convex bodies K, L \subset \mathbb{R}^n (viewed as unit balls) can be made to coincide under affine transformations. Defined as d_{BM}(K, L) = \inf \{ \|T\| \cdot \|T^{-1}\| : T \in GL(n, \mathbb{R}), T(K) = L \}, this distance measures the minimal distortion needed for isomorphism between the corresponding normed spaces. In functional analysis, small Banach-Mazur distance to the Euclidean ball implies near-Hilbertian behavior, with applications to classifying spaces up to isomorphism; for instance, when $1 \leq p \leq q \leq 2, the \ell_p^n and \ell_q^n balls satisfy d_{BM}(\ell_p^n, \ell_q^n) = n^{1/p - 1/q}.^[94] These geometric tools underpin embedding theorems for metric spaces into \ell_p spaces, leveraging convex bodies to bound distortion. Bourgain's theorem states that any n-point metric space embeds into \ell_p (for $1 \leq p \leq \infty) with distortion at most O(\log n), achieved by random projections onto convex sets related to the unit ball of \ell_p. This extends Dvoretzky's ideas to metric embeddings, where the convex geometry of \ell_p balls ensures low-distortion subspaces for arbitrary metrics, with applications to algorithmic dimensionality reduction and coarse geometry. Such embeddings preserve distances up to logarithmic factors, making \ell_p spaces universal targets for finite metrics in functional analytic contexts.

References

[1]
None
Summary of each segment:
[2]
[PDF] An introduction to convex and discrete geometry Lecture Notes
The dimension of a convex set is the dimension of its affine hull. Convexity is clearly preserved by taking intersections. Figure 2.1: An example of a convex ...
[3]
[PDF] ACM 204, FALL 2018: LECTURES ON CONVEX GEOMETRY JOEL ...
Affine geometry. 3. Convex sets and convex hulls. 4. The Carathéodory theorem. 5. Basic topology of convex sets. 6. Extreme points and faces. 1.2 Introduction.
[4]
Convex Optimization – Boyd and Vandenberghe - Stanford University
A MOOC on convex optimization, CVX101, was run from 1/21/14 to 3/14/14. If you register for it, you can access all the course materials.
[5]
https://press.princeton.edu/books/paperback/9780691015866/convex-analysis
[6]
[PDF] Convex and Combinatorial Optimization Fall 2023 Convex Sets
The convex hull of S ⊆ Rn is the smallest convex set containing S. Intersection of all convex sets containing S. The set of all convex combinations of points in ...
[7]
[PDF] Convexity - TTIC
We define the convex hull conv(S) of S as the “smallest” convex set that contains S. Definition 3.1. Consider a set S ⊆ V . Define its convex hull as conv(S) =.
[8]
[PDF] 1 Convex Sets, and Convex Functions
Definition 1.9 The convex hull of a set C is the intersection of all convex sets which contain the set C. We denote the convex hull by co (C). We illustrate ...
[9]
[PDF] CONVEX POLYTOPES
A convex polytope P is defined to be the convex hull of any finite set of points in Ed. A ^-dimensional convex polytope P will be referred to, for brevity, as a.
[10]
[PDF] ``Introduction to Nonlinear Optimization" Lecture Slides - Convex Sets
The Convex Hull. The convex hull conv(S) is “smallest” convex set containing S. Lemma. Let S ⊆ Rn. If S ⊆ T for some convex set T, then conv(S) ⊆ T. Proof.
[11]
[PDF] The Krein–Milman Theorem - A Project in Functional Analysis
Nov 29, 2016 · Theorem (Krein–Milman). A compact convex set K ⊆ E in a normed space coincides with the closed convex hull of its extreme points: K = conv ...
[12]
Convex Combination -- from Wolfram MathWorld
A convex combination of vectors is an expression of the form where sum of lambda_i=1. The set of all convex combinations forms the convex hull.<|separator|>
[13]
[PDF] Convex and Affine Hulls • Caratheodory's Theorem Reading
The convex hull of a compact set is compact. Proof: Let X be compact. We take a sequence in conv(X) and show that it has a convergent sub-.
[14]
[2312.00828] From affine to barycentric coordinates in polytopes
Nov 30, 2023 · Each point of a simplex is expressed as a unique convex combination of the vertices. The coefficients in the combination are the barycentric ...
[15]
[PDF] Affine and Convex Combinations
(a) A set of vectors that is linearly independent must be affinely independent. (b) A set of vectors that is affinely independent must be linearly independent.
[16]
[PDF] 1 Convex and Affine Hulls 2 Caratheodory's Theorem
The convex hull of a set X, denoted by conv(X), is the intersection of all convex sets containing X. The affine hull of a set X, denoted by aff(X), is the ...
[17]
Sur les fonctions convexes et les inégalités entre les valeurs ...
Cite this article. Jensen, J.L.W.V. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math. 30, 175–193 (1906). https://doi.org ...
[18]
None
Below is a merged summary of the definition and examples of convex sets from Chapter 2.1 of "Convex Optimization" by Boyd & Vandenberghe, consolidating all the information provided across the segments. To retain as much detail as possible, I will use a structured format with tables where appropriate, followed by a narrative summary for non-examples and intuition. The response avoids exceeding the thinking token limit by focusing on concise, dense representation.
[19]
[PDF] Jensen's inequality - TTIC
We prove Jensen's inequality for finite M by induction on the number of elements of M. Suppose M contains k elements and assume that Jensen's inequality holds ...
[20]
[PDF] 1. The AM-GM inequality - Berkeley Math Circle
Show that one can derive the AM-GM inequality for positive numbers from Jensen's inequality with f(x) = −log x. 14. Prove xx ≥ x+1. 2 x+1 for x > 0. (Hint ...
[21]
[PDF] E. The Hahn-Banach Theorem - KSU Math
In the remainder of this section we will discuss the geometric form of the. Hahn-Banach theorems. We begin by describing a method of constructing quasi ...
[22]
The Hahn–Banach Theorem | SpringerLink
Dec 1, 2020 · Introduction to Functional Analysis. Download book. PDF · EPUB · Introduction to Functional Analysis pp 71-82 | Cite as. The Hahn–Banach Theorem.Missing: reference | Show results with:reference
[23]
[PDF] 5.5. Geometric Versions of Hahn-Banach Theorem
May 6, 2017 · Note. The Hahn-Banach Separation Theorem deals with “separation” versus “strict separation.” We will see strict separations in Theorem 5.17. ...
[24]
The Hahn–Banach Theorem | An Introduction to Functional Analysis
An Introduction to Functional Analysis · Related content · Chapter 19: The Hahn–Banach Theorem · Authors · Summary · About the book · Our Site · Quick Links · Our ...
[25]
The Hahn—Banach theorem - Springer
Title: The Hahn—Banach theorem ; Book Title: Exercises in Functional Analysis ; Book Part: Part I ; Pages: pp 175-194 ; Copyright: 2003 ...
[26]
[PDF] 1 Radon, Helly and Carathéodory theorems
Sep 16, 2008 · Equivalently, a convex hull of A is the intersection of all convex sets containing A. To see the equivalence in Definition 2, observe that ...<|separator|>
[27]
[PDF] Helly's theorem
It is very tempting and quite usual to formulate Helly's theorem as fol lows: "If every d+l among n convex sets in Rd intersect, then all the sets intersect." ...
[28]
[PDF] Piercing Convex Sets - Princeton Math
The classical theorem of Helly [13] states that any family of compact convex sets in Rd which satisfies the (d + 1,d + 1)-property is 1-pierceable. Hadwiger and ...Missing: dual form
[29]
https://www.csun.edu/~ctoth/Handbook/chap4.pdf
[30]
[PDF] 4 HELLY-TYPE THEOREMS AND GEOMETRIC TRANSVERSALS
Jul 16, 2017 · Similarly, if F is a finite family of convex sets in Rd, then Theorem 4.1.9 implies that if the intersection of every d + 1 or fewer members is ...
[31]
[PDF] Helly's Theorem with Applications in Combinatorial Geometry
Aug 31, 2016 · Helly's Theorem can be generalized to infinite families of convex sets, provided some additional compactness is assumed. Let S be a not ...
[32]
[PDF] Intersecting Families
Theorem: (Erdős-Ko-Rado, 1961). If 2k ≤ n then every intersecting family of ... If n ≥ k+1 convex sets in have the property that any k+1 of them have ...
[33]
[PDF] Combinatorial and Topological Aspects of Helly Type Theorems
Theorem (Alon, Kalai, Matousek, Meshulam): Weak fractional. Helly implies piercing property with the same parameter. Gil Kalai. Combinatorial and Topological ...
[34]
Polytope -- from Wolfram MathWorld
A convex polytope may be defined as the convex hull of a finite set of points (which are always bounded), or as a bounded intersection of a finite set of half- ...
[35]
Simplex -- from Wolfram MathWorld
A simplex, sometimes called a hypertetrahedron (Buekenhout and Parker 1998), is the generalization of a tetrahedral region of space to n dimensions.
[36]
https://www.math.csi.cuny.edu/abhijit/623/euler_slides.pdf
[37]
Cross Polytope -- from Wolfram MathWorld
The cross polytope beta_n is the regular polytope in n dimensions corresponding to the convex hull of the points formed by permuting the coordinates.
[38]
[PDF] Euler's Polyhedral Formula - CSI Math
Euler's Formula. Let P be a convex polyhedron. Let v be the number of vertices, e be the number of edges and f be the number of faces of P. Then.
[39]
[PDF] A Short Proof of Euler–Poincaré Formula - arXiv
Sep 9, 2021 · “V − E + F = 2”, the famous Euler's polyhedral formula, has a natural generalization to convex polytopes in every finite dimension, also known ...
[40]
[PDF] Chapter 8 Shellings, the Euler-Poincaré Formula for Polytopes ...
We will now present the proof that every polytope is shellable, using a technique invented by Bruggesser and. Mani (1970) known as line shelling [?]. We begin ...
[41]
[PDF] 1 Euler's Formula - CSE, IIT Bombay
Corollary 1 In a finite, connected, simple, planar graph, e ≤ 3v−6 if v ≥ 3. If the graph is also bipartite, then e ≤ 2v − 4. Proof: If the graph is simple, ...Missing: source | Show results with:source
[42]
https://link.springer.com/book/10.1007/978-3-0348-5118-3
[43]
Schläfli Symbol -- from Wolfram MathWorld
A symbol of the form {p,q,r,...} used to describe regular polygons, polyhedra, and their higher-dimensional counterparts.
[44]
Theorie der vielfachen Kontinuität - SpringerLink
Nov 21, 2013 · Schläfli. Pages 1-4. Theorie der vielfachen Kontinuität. Theorie ... PDF accessibility summary. This PDF is not accessible. It is based on ...
[45]
Volumen und Oberfläche | Mathematische Annalen
Volumen und Oberfläche. Published: December 1903. Volume 57, pages 447–495, (1903); Cite this article. Download PDF · Mathematische Annalen Aims and scope ...
[46]
[PDF] THE BRUNN-MINKOWSKI INEQUALITY
Oct 25, 2001 · We present a guide that explains the relationship between the Brunn-Minkowski inequality and other inequalities in geometry and analysis, and ...
[47]
On Extensions of the Brunn-Minkowski and Prekopa-Leindler ...
We extend the Prekopa-Leindler theorem to other types of convex com- binations of two positive functions and we strengthen the Prekopa-Leindler.
[48]
On extensions of the Brunn-Minkowski and Prékopa-Leindler ...
Abstract. We extend the Prékopa-Leindler theorem to other types of convex combinations of two positive functions and we strengthen the Prékopa-Leindler and ...
[49]
Convex measures on locally convex spaces - Project Euclid
The purpose of this paper is not to give a complete treatment of so-called convex measures but merely to point out a new technique.
[50]
[PDF] Randomized Urysohn–type inequalities - arXiv
Oct 25, 2019 · As an illustrative example, Urysohn's inequality for convex bodies K ⊆ Rn, relates volume Vn and mean width w, namely,. Vn(K). Vn(B). 1/n. ≤ w ...
[51]
Fritz John
This paper deals with an extension of Lagrange's multiplier rule to the case, where the subsidiary conditions are inequali- ties in~tead of equations.
[52]
The Steiner Formula for Convex Subsets
This chapter is devoted to the computation of the volume of the parallel body of a convex body K at distance ε (see the definition below).
[53]
[PDF] A Course on Convex Geometry
For a set A ⊂ Rn, the polar A◦ is defined as. A◦ := {x ∈ Rn : hx, yi ≤ 1 ∀y ∈ A}. Show that: (a) A◦ is closed, convex and contains 0. (b) If A ⊂ B ...
[54]
Dual Cones - Convex Optimization
The dual cone is critical in tests for convergence by contemporary primal/dual methods for numerical solution of conic problems.
[55]
[PDF] Lecture 7: Dual cones - CSE - IIT Kanpur
So the dual cone is a convex cone irrespective of whether the original cone was convex or not. Notice from the definition the dual cone is always closed too ( ...
[56]
[PDF] Introduction to Convex and Quasiconvex Analysis
Aug 27, 2001 · Using Theorem 46 an important dual representation for closed convex cones can be verified. This result is known as the bipolar theorem and is a ...<|separator|>
[57]
[PDF] Convex Analysis and Nonsmooth Optimization
Mar 29, 2020 · Figure 1.1: Unit balls of `p-norms. on Rn are dual to each other whenever p−1 + q−1 = 1 and p, q ∈ [1,∞].Missing: source | Show results with:source
[58]
[PDF] POLYTOPES OF MAXIMAL VOLUME PRODUCT
A well known result of Santaló [S] (see also [Sc], p. 546) states that in every convex body. K in Rn, there exists a unique point s(K), called the Santaló ...<|control11|><|separator|>
[59]
The Santaló point of a function, and a functional form of the Santaló ...
The Santaló point of a function, and a functional form of the Santaló ... , 8 (1949) 155–161.Google Scholar. [T]. [T]Talagrand, M.. A new isoperimetric ...
[60]
[PDF] Volume product
Observe however that if K has minimal volume product among all other convex bodies, then its Santaló point is also its center of gravity. 3.2. The planar case.
[61]
Symmetric Mahler's conjecture for the volume product in the 3 ...
We prove Mahler's conjecture concerning the volume product of centrally symmetric, convex bodies in Rn R n in the case where n=3 n = 3 .
[62]
A Fourier analytic proof of the Blaschke-Santaló Inequality
Jul 10, 2015 · The Blaschke-Santaló Inequality is the assertion that the volume product of a centrally symmetric convex body in Euclidean space is maximized by ...
[63]
Increasing functions and inverse Santaló inequality for unconditional ...
Mar 1, 2008 · Milman, The Santaló point of a function and a functional form of ... 8, (1949), 155–161. Google Scholar · Download references. Author ...
[64]
[PDF] Lagrange Multipliers Revisited - EliScholar
This Discussion Paper is brought to you for free and open access by the Cowles Foundation at EliScholar – A. Digital Platform for Scholarly Publishing at ...Missing: 403 | Show results with:403
[65]
Nonlinear Programming - Project Euclid
Nonlinear Programming Chapter. Author(s) HW Kuhn, AW Tucker. Editor(s) Jerzy Neyman. Berkeley Symp. on Math. Statist. and Prob., 1951: 481-492 (1951)
[66]
[PDF] The Sagacity of Circles: A History of the Isoperimetric Problem
Accordingly, Zenodorus made use of “theorems proved by Archimedes in his work On the. Sphere and Cylinder” (Thomas 395), thus extending the isoperimetric ...<|control11|><|separator|>
[67]
Twenty-one Proofs of Euler's Formula - UC Irvine
This page lists proofs of the Euler formula: for any convex polyhedron, the number of vertices and faces together is exactly two more than the number of edges.
[68]
[PDF] Cauchy's Work on integral geometry, centers of curvature, and other ...
Nov 30, 2019 · Cauchy proved a formula known today as the Cauchy–Crofton formula (or the ... edition, Oxford,. Clarendon Press, 1958 (first published in 1930).<|control11|><|separator|>
[69]
Geometrie der Zahlen : Minkowski, H. (Hermann), 1864-1909
Apr 5, 2006 · Geometrie der Zahlen. by: Minkowski, H. (Hermann), 1864-1909. Publication date: 1910. Topics: Number theory. Publisher: Leipzig : Teubner.Missing: mixed volumes convex body
[70]
(PDF) From measuring tool to geometrical object: Minkowski's ...
Aug 7, 2025 · ... mixed volumes of convex bodies, which has become a key notion in parts. of convexity theory. 61. He published only one longer paper on his ...
[71]
[PDF] helly's theorem and its relatives1 - Academic Web
Now to prove Helly's theorem for a finite family of convex sets in Rn, we observe first that the theorem is obvious for a family of n + 1 sets.
[72]
Über Systeme von abgeschlossenen Mengen mit ...
Apr 30, 2005 · Über Systeme von abgeschlossenen Mengen mit gemeinschaftlichen Punkten ... Download PDF · Monatshefte für Mathematik und Physik Aims and ...
[73]
[PDF] The Hahn–Banach theorem
The proof of the Hahn–Banach theorem has two parts: First, we show that ℓ can be extended (without increasing its norm) from M to a subspace one dimension ...Missing: outline | Show results with:outline
[74]
https://www.jstor.org/stable/41134272
[75]
[PDF] Dvoretzky's Theorem and Concentration of Measure
Nov 20, 2016 · Dvoretzky's Theorem is a result in convex geometry first proved in 1961 by Aryeh Dvoretzky. In informal terms, the theorem states that every ...
[76]
Minkowski's development of the concept of convex bodies - jstor
Oct 2, 2007 · 38 In Geometrie der Zahlen Minkowski spelled Eichkörper with an A instead of an E. ... While in "Geometrie der Zahlen" he used the nowhere concave ...
[77]
[PDF] Regular Incidence Complexes, Polytopes, and C-Groups - arXiv
Nov 7, 2017 · (1) Regular incidence complexes were introduced around 1977 by Ludwig Danzer as com- binatorial generalizations of regular polytopes [7] ...
[78]
[PDF] convex polytopes - University of Washington Math Department
CONVEX FUNCTIONS ON. CONVEX POLYTOPES. BY. DAVID GALE, VICTOR KLEE AND R. T. ROCKAFELLAR. Reprinted from the. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY.Missing: geometry | Show results with:geometry
[79]
Convex polytopes. Prepared by Volker Kaibel, Victor Klee, and ...
The present chapter contains the fundamental concepts and facts on which we rely in the sequel. Polytopes, their faces and combinatorial types, complexes, ...Missing: seminal | Show results with:seminal
[80]
Shadows of Convex Bodies - jstor
KEITH BALL. ABSTRACT. It is proved that if C is a convex body in Rn then C ... ) This conjecture strengthens the slicing problem mentioned above, namely ...
[81]
[1607.04862] On the average volume of sections of convex bodies
On the average volume of sections of convex bodies. Authors:Silouanos Brazitikos, Susanna Dann, Apostolos Giannopoulos, Alexander Koldobsky.
[82]
Susanna DANN | University of Missouri, Columbia | Research profile
In this paper we study how certain symmetries of convex bodies affect their geometric properties. In particular, we consider the impact of symmetries ...
[83]
[PDF] Lecture 3 1 Geometry of Linear Programs
Sep 2, 2014 · Today we will talk about the geometry of linear programs. First we need some definitions. Definition 1 A set S ⊆ <n is convex if ∀x, y ∈ S, λx ...
[84]
[PDF] Feasible Regions, Feasible and Improving Directions, and ...
– All optimizers form a convex set, and they are on a face of the feasible region. – There is always at least one corner (extreme) optimizer if the feasible ...
[85]
[PDF] Origins of the Simplex Method - DTIC
It is fortunate back in 1947 when algorithms for solving linear programming were first being developed, that the column geometry and not the row geometry was ...
[86]
[PDF] Polytopes and the simplex method - The University of British Columbia
Jan 24, 2021 · Polytopes and the simplex method. 31. This method locates all edges and vertices by the simplex method, indexing the vertices by the set of.
[87]
[PDF] Khachiyan's Linear Programming Algorithm* - cs.wisc.edu
Khachiyan's polynomial time algorithm for determining whether a system of linear inequalities is satisfiable is presented together with a proof of its validity.
[88]
The Ellipsoid Method - PubsOnLine
In February 1979 a note by L. G. Khachiyan indicated how an ellipsoid method for linear programming can be implemented in polynomial time. This.
[89]
[PDF] Interior-point methods for optimization
In Section 2, we discuss self-concordant barriers and their properties, and then describe interior-point methods for both general convex optimization problems ...
[90]
(PDF) Some Geometric Results in Semidefinite Programming
Aug 7, 2025 · PDF | The purpose of this paper is to develop certain geometric results concerning the feasible regions of Semidefinite Programs, called.
[91]
[PDF] an efficient algorith for determining the convex hull of a finite planar set
THE CONVEX HULL OF A FINITE PLANAR SET. R.L. GRAHAM. Bell Telephone Laboratories, Incorporated. Murray Hill, New Jersey, USA. Received 28 January 1972 convex ...
[92]
On the identification of the convex hull of a finite set of points in the ...
On the identification of the convex hull of a finite set of points in the plane. Author links open overlay panel R.A. Jarvis. Show more. Add to Mendeley.
[93]
Voronoi diagrams from convex hulls - ScienceDirect
Voronoi diagrams from convex hulls☆. Author links open overlay panel. Kevin Q ... K.Q. Brown. Fast intersection of half-spaces. Rep. CMU-CS-78-129 ...
[94]
[PDF] Collision Detection: Algorithms and Applications - GAMMA
For each pair of objects whose bounding boxes over- lap, the algorithm checks whether their convex hulls are intersecting based on the closest feature pairs [22] ...
[95]
[PDF] Hybrid Motion Planning Using Minkowski Sums - Robotics
In this paper, we adapt a totally different strategy and focus on more general problems. More specifically, we are interested in developing a planner that is.