Lecture 2: Geometric Background and Convex Hulls (Thursday, Jan 17, 2001) Reading: Chapter 1 in the 4M's. Affine space: We will usually be rather informal in our presentation of geometry, but it is good to start things off on a somewhat formal footing. We begin with some background on Euclidean geometry, which is not presented in the text. There are a number of different geometric systems that can be used to express geometric algorithms: affine geometry, Euclidean geometry, and projective geometry, for example. This semester we will be working almost exclusively with Euclidean geometry, although we may introduce a few concepts from projective geometry later in the semester. We begin with a short review of geometry. Our approach will be different from what is done in most math texts and most computational geometry texts. The standard approach in math texts is to begin by assuming that everything is a ``tuple of real numbers''. But this approach does lend itself to object oriented programming because it blurs the distinction between different geometric elements. The approach in computational geometry texts is to say nothing about geometric representations, but to rely upon an intuitive understanding of geometric concepts. Rather than defining Euclidean geometry we will first define a somewhat more basic geometry called affine geometry. Later we will add one operation, called an inner product, which differentiates Euclidean from affine geometry. An affine geometry consists of a set of scalars (the real numbers), a set of points, and a set of free vectors (or simply vectors). Points are used to specify position. Free vectors are used to specify direction and magnitude, but have no fixed position in space. (This is in contrast to linear algebra where there is no real distinction between points and vectors. However this distinction is useful, since the two are really quite different.) The following are the operations that can be performed on scalars, points, and vectors. Vector operations are just the familiar ones from linear algebra. It is possible to subtract two points. The difference p - q of two points results in a free vector directed from q to p. It is also possible to add a point to a vector. In point vector addition p + v results in the point which is translated by v from p. The following are the legal operations: S * V --> V scalar vector multiplication V + V --> V vector addition P - P --> V point subtraction P + V --> P point vector addition 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.