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 .

What is a Convex Combination?

Given a set of points , we can form an affine combination of these points by selecting constants , (where ) and write

If each is such that , then the point is called a convex combination of the points .

Example - Point on a Line Segment

To give a simple example of this, consider two points and . Any point on the line passing through these two points can be written as

or equivalently

where . The points and in the following figure are affine combinations of and .

The point is a convex combination since . Any point on the line segment joining and 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 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 . The set of all points that can be written as convex combinations of . 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 . (If there were a convex set smaller than the convex hull that contained the points, then we could find a point in the convex hull, but not in the set . But since each of the is in both sets, and the point is a convex combination of the s, it must also be in the convex hull as well as in .) 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 , 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.

This document maintained by Ken Joy