On-Line Computer Graphics Notes
CONVEX COMBINATIONS

Overview

Convex combinations are simply affine combinations where the constants in the combination are limited to be in the interval $[0,1]$.

For a pdf version of these notes look here.

What is a Convex Combination?

Given a set of points ${\bf P} _0, {\bf P} _1, ..., {\bf P} _n$, we can form an affine combination of these points by selecting constants $\alpha_0, \alpha_1, ..., \alpha_n$, (where $\alpha_0 + \alpha_1 + \cdots + \alpha_n = 1$) and write

$${\bf P} \: = \: \alpha_0 {\bf P} _0 + \alpha_1 {\bf P} _1 + \cdots + \alpha_n {\bf P} _n$$

If each $\alpha_i$ is such that $0 \leq \alpha_i \leq 1$, then the point ${\bf P}$ is called a convex combination of the points ${\bf P} _0, {\bf P} _1, ..., {\bf P} _n$.

Example - Point on a Line Segment

To give a simple example of this, consider two points ${\bf P} _0$ and ${\bf P} _1$. Any point ${\bf P}$ on the line passing through these two points can be written as

$${\bf P} \: = \: (1-t) {\bf P} _0 + t {\bf P} _1$$

or equivalently

$${\bf P} = \alpha_0 {\bf P} _0 + \alpha_1 {\bf P} _1$$

where $\alpha_0+\alpha_1=1$. The points ${\bf Q} = \frac{1}{3} {\bf P} _0 + \frac{2}{3} {\bf P} _1$ and ${\bf R} = -\frac{2}{5} {\bf P} _0 + \frac{7}{5} {\bf P} _1$ in the following figure are affine combinations of ${\bf P} _0$ and ${\bf P} _1$.

The point ${\bf Q}$ is a convex combination since $0 \leq \alpha_0, \alpha_1 \leq 1$. Any point on the line segment joining ${\bf P} _0$ and ${\bf P} _1$ can be written as a convex combination.

Convex Set

Given any set of points, we say that the set is a convex set if given any points ${\bf P} _0, {\bf P} _1, ..., {\bf P} _n$ in the set, any convex combination of these points is also in the set. The following figure illustrates both a convex set (on the left) and a non-convex set (on the right).

Since any convex combination of points from a convext set must lie in the set, then certainly the straight line joining any two points of the set must also be completely in the set. This concept is actually quite intuitive, in that if one can draw a straight line between two points of the set that is not completely contained within the set, the the set is not convex.

Convex Hull

Given a set of points ${\bf P} _0, {\bf P} _1, ..., {\bf P} _n$. The set of all points ${\bf P}$ that can be written as convex combinations of ${\bf P} _0, {\bf P} _1, ..., {\bf P} _n$. is called the convex hull of the set. It is easy to see that this convex hull is necessarily a convex set - but, it turns out that it is the smallest convex set that contains ${\bf P} _0, {\bf P} _1, ..., {\bf P} _n$. (If there were a convex set $C$ smaller than the convex hull that contained the points, then we could find a point ${\bf Q}$ in the convex hull, but not in the set $C$. But since each of the ${\bf P} _i$ is in both sets, and the point ${\bf Q}$ is a convex combination of the ${\bf P} _i$s, it must also be in the convex hull as well as in $C$.) The following figure illustrates the convex hull of a set of six points:

We note that one of the six points does not contribute to the boundary of the convex hull. If one looked closely at the coordinates of ${\bf P} _2$, one would find that this point could be written as a convex combination of the other five.

Bibliography

1

DEROSE, T.
Coordinate-free geometric programming.
Technical Report 89-09-16, Department of Computer Science and Engineering, University of Washington, Seattle, Washington, 1994.

Summary

Convex combinations are an extremely important concept in computer graphics and geometric modeling. The convex-hull concept will allow us to take a set of points, put a bounding box about the set of points, and since the bounding box is convex, we are insured that the convex-hull of the set of points is also contained in the bounding box. These bounding boxes are the method that we will use to ``keep track of'' our objects.

Return to the Graphics Notes Home Page
Return to the Geometric Modeling Notes Home Page
Return to the UC Davis Visualization and Graphics Group Home Page

This document maintained by Ken Joy

Mail us your comments

All contents copyright (c) 1996, 1997, 1998, 1999
Computer Science Department
University of California, Davis

All rights reserved.