3.5 Duality and Polar Sets

Duality and polar sets are powerful tools in convex geometry, linking geometric objects to their dual counterparts. They flip vertices to facets, transform convex sets, and provide new perspectives on familiar shapes. This concept is crucial for understanding the relationships between different representations of convex sets and polytopes.

The duality principle extends beyond basic geometry, influencing optimization theory and linear programming. It connects primal and dual problems, offering alternative approaches to solving complex geometric and algebraic challenges in discrete geometry and related fields.

Duality and Polar Sets

Fundamental Concepts of Duality

Top images from around the web for Fundamental Concepts of Duality

• 

  Bipolar theorem - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Dual graph - Wikipedia View original

  Is this image relevant?

• 

  Dual polyhedron - Wikipedia View original

  Is this image relevant?

• 

  Bipolar theorem - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Dual graph - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Fundamental Concepts of Duality

• 

  Bipolar theorem - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Dual graph - Wikipedia View original

  Is this image relevant?

• 

  Dual polyhedron - Wikipedia View original

  Is this image relevant?

• 

  Bipolar theorem - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Dual graph - Wikipedia View original

  Is this image relevant?

1 of 3

• Duality principle establishes a correspondence between geometric objects and their dual counterparts
• Polar set represents the dual of a convex set, consisting of all linear functionals bounded by 1 on the original set
• Dual polytope emerges as the polar set of a polytope, inverting vertices to facets and vice versa
• Bipolar theorem states that the polar of the polar set equals the closure of the convex hull of the original set and the origin

Properties and Applications of Polar Sets

• Polar sets preserve convexity, transforming convex sets into convex sets in the dual space
• Intersection of polar sets corresponds to the sum of the original sets: $(A + B)° = A° ∩ B°$
• Sum of polar sets equates to the polar of the intersection of the original sets: $(A ∩ B)° = A° + B°$
• Polar sets find applications in optimization theory, particularly in linear programming duality

Geometric Interpretations and Examples

• Dual polytope of a cube results in an octahedron, illustrating the vertex-facet inversion
• Polar set of a circle centered at the origin remains unchanged, demonstrating self-duality
• Dual of a triangle produces another triangle with vertices corresponding to the original's edge normals
• Bipolar theorem application shows that the polar of a line segment through the origin yields a strip in the dual space

Hyperplanes and Half-spaces

Definitions and Basic Properties

• Hyperplane represents an (n-1)-dimensional subspace in an n-dimensional space, defined by a linear equation
• Half-space consists of all points on one side of a hyperplane, including the hyperplane itself
• Supporting hyperplane touches a convex set at one or more boundary points without intersecting its interior
• Polar cone comprises all vectors forming non-acute angles with every vector in the original cone

Geometric Relationships and Duality

• Hyperplanes in primal space correspond to points in dual space, establishing a one-to-one relationship
• Half-spaces in primal space translate to half-spaces containing the origin in dual space
• Supporting hyperplanes of a convex set relate to boundary points of its polar set
• Polar cone of a convex cone equals the negative of its dual cone: $C^* = -C°$

Applications in Convex Geometry

• Hyperplanes serve as decision boundaries in machine learning algorithms (support vector machines)
• Half-spaces play a crucial role in defining convex polytopes as intersections of finite half-spaces
• Supporting hyperplanes help characterize extreme points and faces of convex sets
• Polar cones find use in optimization theory, particularly in formulating dual problems

Theorems and Lemmas

Fundamental Theorems in Convex Geometry

• Minkowski-Weyl theorem states that every convex polytope can be represented as the convex hull of its vertices or the intersection of half-spaces
• Farkas' lemma provides conditions for the existence of solutions to systems of linear inequalities
• Polar coordinates offer an alternative representation of points in a plane, using distance from the origin and angle from a reference direction

Applications and Implications

• Minkowski-Weyl theorem enables dual representations of polytopes, facilitating computational geometry algorithms
• Farkas' lemma finds applications in linear programming, proving the duality theorem and optimality conditions
• Polar coordinates simplify certain geometric problems, particularly those involving circular or radial symmetry

Extended Concepts and Related Results

• Generalized Farkas' lemma extends to non-linear convex functions and convex cones
• Carathéodory's theorem relates to Minkowski-Weyl, bounding the number of points needed to represent a convex combination
• Helly's theorem provides conditions for the intersection of convex sets, with implications for linear programming

Voronoi and Delaunay Duality

Voronoi Diagrams and Delaunay Triangulations

• Voronoi diagram partitions a plane into regions based on proximity to a given set of points
• Delaunay triangulation connects points to form triangles, maximizing the minimum angle of all triangles
• Duality between Voronoi diagrams and Delaunay triangulations establishes a one-to-one correspondence between their elements

Properties and Applications of Dual Structures

• Voronoi vertices correspond to circumcenters of Delaunay triangles
• Voronoi edges intersect Delaunay edges perpendicularly
• Delaunay triangulation minimizes the maximum circumradius among all possible triangulations
• Applications span computational geometry, computer graphics, and geographic information systems

Reciprocal Lattices and Extended Concepts

• Reciprocal lattice represents the Fourier transform of a crystal lattice in solid-state physics
• Brillouin zones in reciprocal space relate to Wigner-Seitz cells in real space, exhibiting duality
• Higher-dimensional generalizations include Voronoi tessellations and Delaunay complexes
• Power diagrams extend Voronoi diagrams to weighted point sets, preserving duality with regular triangulations