Overview
Convex combinations are simply affine combinations where the constants in the combination are limited to be in the interval .
For a pdf version of these notes look here.
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
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
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.
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
All contents copyright (c) 1996, 1997, 1998,
1999
Computer Science Department
University of California, Davis
All rights reserved.