Convex set

A con­vex set is a set of vec­tors that con­tains all line seg­ments be­tween vec­tors in the set. Con­sider the fol­low­ing shape:

a convex set

As shown, a line seg­ment be­tween two points \(x\) and \(y\) in this shape lies en­tirely within the shape. In fact, this is true for any pair of points in the shape. There­fore, this shape is con­vex. For com­par­i­son, the fol­low­ing shape is not con­vex:

a non-convex set

The fact that part of the line seg­ment be­tween \(x\) and \(y\) (both in­side the shape) lies out­side the shape proves that this shape is not con­vex.

For­mally, a set \(S\) is con­vex if

$$\forall x, y \in S, \theta \in [0, 1]: \theta x + (1 - \theta) y \in S$$

(images are from Wikipe­dia: here and here)

use non-Wikipe­dia images and re­move the attribution

Parents:

  • Set

    An un­ordered col­lec­tion of dis­tinct ob­jects.

  • Convex