📐Discrete Geometry Unit 3 – Convex Sets and Polytopes

Key Concepts and Definitions

• Convex set defined as a set of points where any two points in the set can be connected by a line segment that is entirely contained within the set
• Convex hull refers to the smallest convex set that contains a given set of points
• Affine combination is a linear combination of points where the coefficients sum to 1
• Convex combination is an affine combination with non-negative coefficients
• Extreme point is a point in a convex set that cannot be expressed as a convex combination of other points in the set
  • Also known as a vertex in the context of polytopes
• Supporting hyperplane is a hyperplane that intersects a convex set and has the entire set on one side of it
• Separating hyperplane is a hyperplane that separates two disjoint convex sets

Fundamental Properties of Convex Sets

• Intersection of any collection of convex sets is also a convex set
• Union of two convex sets is convex if and only if their intersection is non-empty
• Scaling a convex set by a positive factor preserves convexity
• Translation of a convex set by any vector preserves convexity
• Projection of a convex set onto a subspace is a convex set
  • Useful in dimensionality reduction and optimization problems
• Convex sets are connected and simply connected
• Convex sets have a well-defined boundary and interior
  • Interior points can be expressed as convex combinations of other points in the set

Types of Convex Sets

• Hyperplanes and halfspaces are the simplest examples of convex sets
• Euclidean balls and ellipsoids are convex sets defined by quadratic inequalities
• Polyhedra are convex sets defined by finitely many linear inequalities
  • Includes polytopes as bounded polyhedra
• Cones are convex sets closed under positive scaling
  • Useful in modeling optimization problems and feasible regions
• Norm balls are convex sets defined by a norm function (e.g., $L_1$, $L_2$, $L_\infty$ norms)
• Epigraphs of convex functions are convex sets in higher dimensions
• Zonoids are convex sets that can be represented as the Minkowski sum of line segments

Introduction to Polytopes

• Polytopes are bounded intersections of finitely many halfspaces
• Vertices, edges, and faces are key elements of polytopes
  • Vertices are extreme points of the polytope
  • Edges are line segments connecting two vertices
  • Faces are lower-dimensional intersections of the polytope with its supporting hyperplanes
• Polytopes can be represented as the convex hull of a finite set of points (V-representation)
• Polytopes can also be represented as the intersection of finitely many halfspaces (H-representation)
• Simplices are the simplest polytopes with $n+1$ vertices in $n$-dimensional space
  • Examples include line segments, triangles, and tetrahedra

Representation and Characterization of Polytopes

• V-representation and H-representation are dual to each other
  • Conversion between the two representations is a fundamental problem in computational geometry
• Facets are the highest-dimensional faces of a polytope
  • Correspond to the defining inequalities in the H-representation
• Vertex enumeration is the problem of finding all vertices of a polytope given its H-representation
• Facet enumeration is the problem of finding all facets of a polytope given its V-representation
• Euler's formula relates the number of vertices, edges, and faces of a polytope
  • $V - E + F = 2$ for 3-dimensional polytopes
• Combinatorial properties of polytopes can be studied using face lattices and Gale diagrams

Algorithms and Computational Aspects

• Convex hull algorithms compute the convex hull of a given set of points
  • Examples include Graham's scan, Quickhull, and the incremental algorithm
• Linear programming optimizes a linear objective function over a polyhedron
  • Simplex method is a classical algorithm for solving linear programs
  • Interior point methods are more efficient for large-scale problems
• Vertex enumeration algorithms include the double description method and the reverse search method
• Facet enumeration algorithms include the beneath-beyond method and the gift-wrapping algorithm
• Polytope volume computation is a challenging problem with applications in integration and probability
  • Triangulation methods and Monte Carlo methods are commonly used

Applications in Optimization and Modeling

• Linear programming is widely used in operations research, economics, and resource allocation problems
• Integer programming optimizes a linear objective function over the integer points in a polyhedron
  • Useful in modeling combinatorial optimization problems
• Semidefinite programming optimizes a linear objective function over the cone of positive semidefinite matrices
  • Applications in control theory, graph theory, and approximation algorithms
• Polyhedral combinatorics studies combinatorial optimization problems using polyhedral techniques
  • Examples include the traveling salesman problem and the maximum cut problem
• Convex relaxations replace non-convex constraints with convex ones to obtain tractable approximations
  • Widely used in machine learning, signal processing, and computer vision

Advanced Topics and Open Problems

• Ehrhart theory studies the integer points in dilations of a polytope
  • Connects discrete geometry with generating functions and complex analysis
• Toric varieties are algebraic varieties associated with rational polytopes
  • Bridge between discrete geometry and algebraic geometry
• Polytope algebra studies the algebraic structure of the space of polytopes
  • Includes Minkowski addition, Hadwiger's theorem, and the Alexandrov-Fenchel inequality
• Approximation of convex sets by polytopes is a fundamental problem in convex geometry
  • Relates to the complexity of convex bodies and the geometry of numbers
• The Hirsch conjecture on the diameter of polytope graphs is a long-standing open problem
  • Conjectured that the diameter is at most $n-d$ for a $d$-dimensional polytope with $n$ facets
• The polynomial Hirsch conjecture asks whether there is a polynomial upper bound on the diameter
  • Relates to the complexity of the simplex method in linear programming