2.1 Definition and properties of convex hulls

Convex hulls are like invisible rubber bands wrapping around a set of points. They're the smallest convex shape that contains all the points, with some special properties. Understanding convex hulls is key to grasping many geometric concepts.

Building and analyzing convex hulls involves clever algorithms and mathematical tricks. We'll look at how to construct them in 2D and 3D, and learn ways to check if a point is inside the hull. These skills are super useful in computer graphics and computational geometry.

Understanding Convex Hulls

Definition of convex hulls

Top images from around the web for Definition of convex hulls

• 

  Legendre transform – foreXiv View original

  Is this image relevant?

• 

  mg.metric geometry - Convex hull on a Riemannian manifold - MathOverflow View original

  Is this image relevant?

• 

  VTK/Examples/Cxx/PolyData/ConvexHullShrinkWrap - KitwarePublic View original

  Is this image relevant?

• 

  Legendre transform – foreXiv View original

  Is this image relevant?

• 

  mg.metric geometry - Convex hull on a Riemannian manifold - MathOverflow View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition of convex hulls

• 

  Legendre transform – foreXiv View original

  Is this image relevant?

• 

  mg.metric geometry - Convex hull on a Riemannian manifold - MathOverflow View original

  Is this image relevant?

• 

  VTK/Examples/Cxx/PolyData/ConvexHullShrinkWrap - KitwarePublic View original

  Is this image relevant?

• 

  Legendre transform – foreXiv View original

  Is this image relevant?

• 

  mg.metric geometry - Convex hull on a Riemannian manifold - MathOverflow View original

  Is this image relevant?

1 of 3

• Convex hull envelops smallest convex set containing given points minimizes enclosed area or volume
• Intersection of all convex sets containing given set creates unique boundary
• Geometric interpretation visualizes rubber band stretched around 2D points or shrink-wrap enclosing 3D objects
• Formal mathematical definition expresses convex hull as $CH(S) = \{∑_{i=1}^n λ_i x_i : x_i ∈ S, λ_i ≥ 0, ∑_{i=1}^n λ_i = 1\}$
• Extreme points lie on convex hull boundary cannot be expressed as convex combinations of other set points

Properties of convex hulls

• Convexity ensures line segment between any two hull points lies entirely within hull
• Uniqueness guarantees only one convex hull exists for given point set
• Invariance under affine transformations preserves convex hull shape during translation, rotation, scaling
• Dimension matches affine hull of original set maintains geometric characteristics
• Closure property makes convex hull a closed set includes all its boundary points
• Compactness of convex hull follows from compactness of original set bounded and closed
• Containment relationship original set always subset of its convex hull

Constructing and Analyzing Convex Hulls

Construction of convex hulls

• 2D construction methods include:
  1. Graham scan algorithm:
     • Select pivot point (lowest y-coordinate)
     • Sort remaining points by polar angle
     • Traverse sorted points, maintain stack of hull vertices
  2. Jarvis march (gift wrapping) algorithm:
     • Start with leftmost point
     • Find next hull vertex with smallest polar angle
     • Repeat until reaching start point
• 3D construction methods encompass:
  1. Incremental algorithm:
     • Add points one by one
     • Update hull structure with each addition
  2. Divide-and-conquer approach:
     • Recursively construct hulls of subsets
     • Merge sub-hulls to form complete 3D hull
• Computational complexity varies:
  • 2D optimal algorithms achieve $O(n \log n)$ time
  • 3D output-sensitive algorithms reach $O(n \log n)$ efficiency

Point inclusion in convex hulls

• Point-in-polygon test for 2D employs ray casting or winding number algorithms
• Halfspace intersection test checks if point satisfies all hull-defining halfspace constraints
• Barycentric coordinate test expresses point as convex combination of hull vertices
• Extreme point check determines inclusion based on point's extremality
• Computational geometry libraries offer efficient implementations for testing (CGAL, Boost.Geometry)