Figure 4: Affine operations.
A number of operations can be derived from these. For example, we can
define the subtraction of two vectors u - v as u+ (-1 * v) or scalar
vector division v/a as (1/a) * v provided a ~= 0.
There is one special vector, called the zero vector, 0, which has no
magnitude, such that v + 0 = v. Note that it is not possible to
multiply a point times a scalar or to add two points together.
However there is a special operation that combines these two elements,
called an affine combination. Given any scalar a and two points
p and q , define the affine combination Aff(p,q,a) to be:
(1 - a) * p + a * q = p + a * (p - q)
Note that the left-hand side of this equation is not legal given
our list of operations. But this is how the affine combination is
typically expressed, namely as the weighted average of two points. The
right-hand side (which is easily seen to be algebraically
equivalent) is legal.
An important observation is that, if p ~= q , then the point
Aff(p,q,a) lies on the line connecting p and q, and generally, as
a varies from -INF to +INF it traces out all the points on this line.
Figure 5: Affine combination.
In the special case where 0 < a < 1, Aff(p,q,a) is a point that
subdivides the line segment pq into two subsegments of relative sizes
a to 1-a. When a is in this range, the operation is called a convex
combination, and the set of all convex combinations traces out the
line segment pq . It is easy to extend both types of combinations to
more than two points, by adding the condition that the sum of
coefficients sums to 1.
Homogeneous Coordinates: In order to assign coordinates to points and
vectors, we assume that there is a designated standard coordinate
system, which is specified by an origin point and d orthogonal unit
vectors. To represent vectors and points in affine space, it is often
convenient to use homogeneous coordinates. Suppose that we are working
in d-dimensional affine space. It is common to represent both free
vectors and points as (d + 1)-tuples of real numbers. To represent a
free vector we take its standard d-tuple of coordinates an prepend an
additional 0 to the beginning. To represent a point we take its
d-tuple and prepend an additional 1. (In many application areas,
graphics and solid-modeling in particular, it is common to append the
0 or 1 to the end of the tuple. In principal there is no reason that
one representation is better than the other, but beware that the
concept of orientation defined below is reversed in odd dimensions in
this case.)
This may sound rather ad-hoc, but it has some very nice algebraic
properties. For example, if you take the difference of two points
(which results in a free vector) observe that by simply subtracting
their homogeneous coordinate tuples, component by component, you will
get the proper representation of this free vector (since the first two
coordinates will cancel each other giving 0). We will sometimes be
sloppy. When it is clear that we are dealing with points, we may drop
the homogenizing coordinate.
Figure 6: Homogeneous coordinates.
Orientation: In order to make discrete decisions, we need a geometric
operation that is somewhat analogous to the relational operations (< ,
= , >) with numbers. There does not sem to be any natural intrinsic
way to compare two points in d-dimensional space, but there is a
natural relation between ordered (d + 1)-tuples of points in d-space,
which extends the notion of relations in 1-space, called orientation.
Given an ordered triple of three points (p,q,r) in the plane, we say
that they have positive orientation if they define a counterclockwise
oriented triangle, negative orientation if they define a clockwise
oriented triangle, and zero orientation if they are collinear. Note
that orientation depends on the order in which the points are
given. In general, given an ordered 4-tuple points in 3-space, we can
also define their orientation as being either positive (forming a
right-handed screw), negative (a left-handed screw), or zero
(coplanar). This can be generalized to any ordered (d + 1)-tuple
points in d-space.
Figure 7: Orientations of the ordered triple (p; q; r).
Orientation is formally defined as the sign of the determinant of the
points given in homoge- neous coordinates. For example, in the plane,
we have Orient(p,q,r) = determinant of the matrix:
1 px py
1 qx qy
1 rx ry
Observe that in the 1-dimensional case, Orient(p,q) is just q -
p. Hence it is positive if p < q, zero if p = q, and negative if p >
q. Thus orientation generalized <,=,> in 1-dimensional space.
Convexity: Now that we have discussed some of the basics, let us
consider an initial problem. The computation of convex hulls is among
the most basic problems in computational geometry. An O(n log n)
algorithm for computing convex hulls was one of the earliest results
in computational geometry (due to Ron Graham). The convex hull can be
defined intuitively by surrounding a collection of points with a
rubber band and letting the rubber band snap tightly around the
points.
There are a number of reasons that the convex hull of a point set is
an important geometric structure. One is that it is one of the
simplest shape approximations for a set of points. Also many
algorithms compute the convex hull as an initial stage in their
execution, because convex polygons are often easier to deal with than
point sets. For example, in order to find the smallest rectangle or
triangle that encloses a set of points, it suffices to first compute
the convex hull of the points, and then find the smallest rectangle or
triangle enclosing the hull.
Convexity: A set S is convex if given any points (p,q) in S any convex
combination of p and q is in S, or equivalently, the line segment pq
is in S.
Convex hull: The convex hull of any set S is the intersection of all
convex sets that contains S, or more intuitively, the smallest convex
set that contains S. Following our book's notation, we will denote
this CH(S). An equivalent definition of convex hull is the set of
points that can be expressed as convex combinations of the points in
S. (A proof can be found in any book on convexity theory.) A convex
combination of three or more points is an linear combination of the
points in which the coefficients sum to 1 and all the coefficients are
in the interval [0; 1]. In general, convex sets may have either
straight or curved boundaries, may be bounded or unbounded (e.g. an
infinite cone is convex), and may be topologically open or closed
(that is, they may or may not contain their boundary). The convex hull
of a finite set of points is necessarily a bounded, closed, convex
polygon.
Convex hull problem: The (planar) convex hull problem is, given a set
of n points P in the plane, output the vertices of the convex
hull. Normally, polygons are presented in counterclockwise order. For
some reason our book outputs the hull in clockwise order, but
obviously it is a trivial matter to convert from one to the other. The
hull should consist only of extreme points, in the sense that if three
points lie on an edge of the convex hull, then the middle point should
not be output as part of the hull.
The book introduces a simple O(n^3) convex hull algorithm, which
operates by considering each ordered pair of points (p, q), and the
determining whether all the remaining points of the set lie within the
half-plane lying to the right of the directed line from p to
q. (Observe that this can be tested using the orientation test.) The
question is, can we do better?
Graham's scan: We will present an O(n log n) algorithm for convex
hulls. It is a simple variation of a famous algorithm for convex
hulls, called Graham's scan. This algorithm dates back to the early
70's. The algorithm is based on an approach called incremental
construction, in which points are added one at a time, and the hull is
updated with each new insertion. If we were to add points in some
arbitrary order, we would need some method of testing whether points
are inside the existing hull or not. To avoid the need for this test,
we will add points in increasing order of x-coordinate, thus
guaranteeing that each newly added point is outside the current
hull. (Note that Graham's original algorithm sorted points in a
different way. It found the lowest point in the data set and then
sorted points cyclically around this point.)
Since we are working from left to right, it would be convenient if the
convex hull vertices were also ordered from left to right. The convex
hull is a cyclically ordered sets. Cyclically ordered sets are
somewhat messier to work with than simple linearly ordered sets, so we
will break the hull into two hulls, an upper hull and lower hull. The
break points common to both hulls will be the leftmost and rightmost
vertices of the convex hull. After building both, the two hulls are
merged into a single cyclic list.
Let us consider the upper hull, since the lower hull is symmetric.
Let p1,p2... pn denote the set of points, sorted by increase
x-coordinates. As we walk around the upper hull from left to right,
observe that each consecutive triple along the hull makes a right-hand
turn. That is, if p,q,r are consecutive points along the upper hull,
then Orient(p,q,r) < 0. When a new point pi is added to the current
hull, this may violate the right-hand turn invariant. So we check the
last three points on the upper hull, including pi. If They fail to
form a right-hand turn, then we delete the point prior to pi . This is
repeated until the number of points on the upper hull (including pi)
is less than three, or the right-hand turn condition is
reestablished. See the text for a complete description of the code. We
have ignored a number of special cases. We will consider these next
time.
Figure 9: Convex hulls and Graham's scan.
Analysis: Let us prove the main result about the running time of Graham's scan.
Theorem: Graham's scan runs in O(n log n) time.
Proof: Sorting the points according to x-coordinates can be done by
any efficient sorting algorithm in O(n log n) time. For each point
added, the amount of time spent is clearly O(Di + 1), where Di is
the number of points deleted in the process of adding point pi . The
reason is that each orientation test takes constant time, and we must
perform one orientation test for each point deleted, perhaps along
with one extra one (for the last point which is not deleted). Thus,
the total running time is proportional to
Sum(i=1..n) [ (Di + 1) ] = n + Sum(i=1..n) [Di]
How large is Sum[Di] ?
Observe that once a point is deleted, it can never be deleted
again. Since each of n points can be deleted at most once, Sum[Di] <
n. Thus after sorting, the total running time is O(n). Since this is
true for the lower hull as well, the total time is O(2n) = O(n).
This course is modeled on the Computational Geometry Course taught by Dave Mount, at the University of Maryland. These notes are modifications of his Lecture Notes, which are copyrighted as follows: Copyright, David M. Mount, 2000, Dept. of Computer Science, University of Maryland, College Park, MD, 20742. These lecture notes were prepared by David Mount for the course CMSC 754, Computational Geometry, at the University of Maryland, College Park. Permission to use, copy, modify, and distribute these notes for educational purposes and without fee is hereby granted, provided that this copyright notice appear in all copies.