A set is convex if for every two points in the set, the entire line segment between them lies in the set. No dents, no holes. Convexity is the geometric property that makes optimization tractable: every local minimum is global.
Convex sets
A set S is convex when for all x, y in S and all t in [0, 1], the point tx + (1-t)y is also in S. A circle is convex. A star shape is not. The intersection of any family of convex sets is convex. The empty set and all of R^n are convex.
Scheme
; Test if a point is inside a convex polygon; A convex polygon: all cross products have the same sign
(define (cross-2d ox oy ax ay bx by)
(- (* (- ax ox) (- by oy))
(* (- ay oy) (- bx ox))))
; Square with vertices (0,0), (4,0), (4,4), (0,4)
(define square-verts
(list (list 00) (list 40) (list 44) (list 04)))
; Check convexity: walk edges, all cross products same sign
(define (convex? verts)
(let* ((n (length verts))
(signs
(map (lambda (i)
(let* ((a (list-ref verts i))
(b (list-ref verts (modulo (+ i 1) n)))
(c (list-ref verts (modulo (+ i 2) n))))
(cross-2d (car a) (cadr a)
(car b) (cadr b)
(car c) (cadr c))))
(iota n))))
(or (for-all (lambda (s) (> s 0)) signs)
(for-all (lambda (s) (< s 0)) signs))))
(define (for-all pred lst)
(cond ((null? lst) #t)
((pred (car lst)) (for-all pred (cdr lst)))
(else#f)))
(define (iota n)
(let loop ((i 0) (acc (list)))
(if (>= i n) (reverse acc) (loop (+ i 1) (cons i acc)))))
(display "Square convex? ")
(display (convex? square-verts)) (newline)
; Star shape (non-convex)
(define star-verts
(list (list 20) (list 2.51.5) (list 42) (list 2.52.5)
(list 24) (list 1.52.5) (list 02) (list 1.51.5)))
(display "Star convex? ")
(display (convex? star-verts))
Python
def cross_2d(o, a, b):
return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
def is_convex(verts):
n = len(verts)
signs = [cross_2d(verts[i], verts[(i+1)%n], verts[(i+2)%n]) for i inrange(n)]
returnall(s > 0for s in signs) orall(s < 0for s in signs)
square = [(0,0), (4,0), (4,4), (0,4)]
star = [(2,0),(2.5,1.5),(4,2),(2.5,2.5),(2,4),(1.5,2.5),(0,2),(1.5,1.5)]
print(f"Square convex? {is_convex(square)}")
print(f"Star convex? {is_convex(star)}")
Convex hull
The convex hull of a set of points is the smallest convex set containing them. Think of stretching a rubber band around the points: the hull is the shape the band makes. Computing the convex hull of n points can be done in O(n log n) time. Graham scan is the classic algorithm.
Scheme
; Convex hull via gift wrapping (Jarvis march); Simpler to implement than Graham scan
(define (cross-2d o a b)
(- (* (- (car a) (car o)) (- (cadr b) (cadr o)))
(* (- (cadr a) (cadr o)) (- (car b) (car o)))))
(define (leftmost points)
(let loop ((pts (cdr points)) (best (car points)))
(if (null? pts) best
(loop (cdr pts)
(if (< (car (car pts)) (car best)) (car pts) best)))))
(define (jarvis-hull points)
(let* ((start (leftmost points))
(hull (list start)))
(let loop ((current start) (hull hull))
(let ((next (car points)))
(let inner ((pts (cdr points)) (best next))
(if (null? pts)
(if (equal? best start)
(reverse hull)
(loop best (cons best hull)))
(inner (cdr pts)
(if (> (cross-2d current best (car pts)) 0)
(car pts) best))))))))
(define pts (list (list 00) (list 13) (list 21)
(list 34) (list 40) (list 22)))
(display "Points: ") (display pts) (newline)
(display "Hull: ") (display (jarvis-hull pts))
Separation theorems
If two convex sets are disjoint, there exists a hyperplane that separates them: one set lies entirely on one side, the other set on the other side. This is the hyperplane separation theorem. It is the geometric foundation of support vector machines, linear programming duality, and the Hahn-Banach theorem.
Support functions
The support function h(d) of a convex set S gives the signed distance from the origin to the supporting hyperplane with outward normal d. It encodes the shape of S completely: knowing h(d) for every direction d lets you reconstruct S. The Minkowski sum of two sets has a support function equal to the sum of their support functions.
Scheme
; Support function: h_S(d) = max over x in S of (d . x); For a convex polygon, check all vertices
(define (dot u v)
(+ (* (car u) (car v)) (* (cadr u) (cadr v))))
(define (support-fn vertices direction)
(apply max (map (lambda (v) (dot direction v)) vertices)))
; Unit square: vertices (0,0), (1,0), (1,1), (0,1)
(define square (list (list 00) (list 10) (list 11) (list 01)))
; Support in direction (1, 0) = rightmost extent = 1
(display "h(1,0) = ") (display (support-fn square (list 10))) (newline)
; Support in direction (0, 1) = topmost extent = 1
(display "h(0,1) = ") (display (support-fn square (list 01))) (newline)
; Support in direction (1, 1) = top-right corner
(display "h(1,1) = ") (display (support-fn square (list 11))) (newline)
; Support in direction (-1, 0) = leftmost = 0
(display "h(-1,0) = ") (display (support-fn square (list -10)))
Minkowski sum
The Minkowski sum A + B is the set of all points a + b where a is in A and b is in B. If A is a polygon and B is a disk, A + B is A with rounded corners. Minkowski sums are used in robotics (configuration space obstacles), morphology (dilation), and collision detection. The Minkowski sum of two convex polygons is convex and computable in O(n + m) time.
Scheme
; Minkowski sum of two convex polygons; Merge sorted edge lists by angle; For finite point sets, brute force: all pairwise sums
(define (minkowski-sum-brute A B)
(apply append
(map (lambda (a)
(map (lambda (b)
(list (+ (car a) (car b))
(+ (cadr a) (cadr b))))
B))
A)))
; Triangle + small square
(define triangle (list (list 00) (list 20) (list 12)))
(define small-sq (list (list 00) (list 0.50) (list 0.50.5) (list 00.5)))
(define msum (minkowski-sum-brute triangle small-sq))
(display "Triangle + Square vertices:") (newline)
(for-each (lambda (p) (display " ") (display p) (newline)) msum)
(display "Count: ") (display (length msum))
; Hull of these gives the Minkowski sum polygon
The convex hull algorithm shown is Jarvis march (gift wrapping), which runs in O(nh) time where h is the number of hull vertices. Graham scan achieves O(n log n) regardless of output size. The separation theorem stated here is the finite-dimensional version; the infinite-dimensional generalization (Hahn-Banach) requires additional hypotheses (closedness, or one set having nonempty interior).
Convex set,