Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| convex combination | two distinct points p1 = (x1, y1) and p2 = (x2, y2) is any point
p3 = (x3, y3) such that for some αy1 + (1 - α)y2. p3 = αp1 + (1 - α)p2. Intuitively, p3 is any point that is on the line passing through p1 and p2 and is on or between p1 and p2 on the line.
(See page 934)
|
 |
|
|
| line segment | Given two distinct points p1 and p2, the line segment is the set of convex combinations of p1 and p2.
(See page 934)
|
|
|
|
| cross product | p1 x p2 can be interpreted as the signed area of the parallelogram formed by the points (0, 0), p1, p2, and p1 + p2 = (x1 + x2, y1 + y2).
(See page 934)
|
|
|
|
| colinear | pointing in either the same or opposite directions
(See page 935)
|
|
|
|
| polar angle | of a point p1 with respect to an origin point p0 is the angle of the vector p1 - p0 in the usual polar coordinate system.
(See page 939)
|
|
|
|
| polygon | a piecewise-linear, closed curve in the plane.
(See page 939)
|
|
|
|
| sides | a sequence of straight-line segments, in a curve ending on itself called a polygon.
(See page 939)
|
|
|
|
| vertex | of a polygon is a point joining two consecutive sides.
(See page 939)
|
|
|
|
| simple | polygon which does not cross itself.
(See page 939)
|
|
|
|
| interior | of a polygon is the set of points in the plane enclosed by a simple polygon.
(See page 939)
|
|
|
|
| boundary | formed by the set of points on the polygon itself.
(See page 939)
|
|
|
|
| exterior | formed by the set of points surrounding a polygon.
(See page 939)
|
|
|
|
| convex | A simple polygon is convex if, given any two points on its boundary or in its interior, all points on the line segment drawn between them are contained in the polygon's boundary or interior.
(See page 939)
|
|
|
|
| right horizontal ray | Given a point p0 = (x0, y0), the right horizontal ray from p0 is the set of points {pi = (xi, yi) : xi ≥ x0 and yi = y0}, that is, it is the set of points due right of p0 along with p0 itself.
(See page 940)
|
|
|
|
| sweeping | an imaginary vertical sweep line passes through the given set of geometric objects, usually from left to right. The spatial dimension that the sweep line moves across, in this case the x-dimension, is treated as a dimension of time. Sweeping provides a method for ordering geometric objects, usually by placing them into a dynamic data structure, and for taking advantage of relationships among them.
(See page 940)
|
|
|
|
| comparable | segments are comparable at x if the vertical sweep line with x-coordinate x intersects both of them.
(See page 941)
|
|
|
|
| above | s1 is above s2 at x, written s1 >x s2, if s1 and s2 are comparable at x and the intersection of s1 with the sweep line at x is higher than the intersection of s2 with the same sweep line.
(See page 941)
|
|
|
|
| sweep-line status | gives the relationship among the objects intersected by the sweep line.
(See page 942)
|
|
|
|
| event-point schedule | a sequence of x-coordinates, ordered from left to right, that defines the halting positions of the sweep line. Each halting position is called an event point. Changes to the sweep-line status occur only at event points.
(See page 942)
|
|
|
|
| covertical | two or more endpoints which have the same x-coordinate
(See page 942)
|
|
|
|
| convex hull | of a sest Q of points is the smallest convex polygon P for which each point in Q is either on the boundary of P or in its interior.
(See page 947)
|
|
|
|
| incremental method | The points are sorted from left to right, yielding a sequence
⟨p1, p2, . . . , pn⟩. At the ith stage, the convex hull of the i - 1 leftmost points,
CH({p1, p2, . . . , pi-1}), is updated according to the ith point from the left, thus forming CH({p1, p2, . . . , pi}).
(See page 948)
|
|
|
|
| divide-and-conquer method | in Θ(n) time the set of n points is divided into two subsets, one containing the leftmost ⌈n/2⌉ points and one containing the rightmost ⌊n/2⌋ points, the convex hulls of the subsets are computed recursively, and then a clever method is used to combine the hulls in O(n) time.
(See page 948)
|
|
|
|
| prune-and-search method | similar to the worst-case linear-time median algorithm of Section 9.3. It finds the upper portion (or "upper chain") of the convex hull by repeatedly throwing out a constant fraction of the remaining points until only the upper chain of the convex hull remains. It then does the same for the lower chain.
(See page 948)
|
|
|
|
| farthest-pair problem | given a set of n points in the plane, find the two points whose distance from each other is maximum. These two points must be vertices of the convex hull.
(See page 948)
|
|
|
|
| Graham's scan | solves the convex-hull problem by maintaining a stack S of candidate points. Each point of the input set Q is pushed once onto the stack, and the points that are not vertices of CH(Q) are eventually popped from the stack. When the algorithm terminates, stack S contains exactly the vertices of CH(Q), in counterclockwise order of their appearance on the boundary.
(See page 949)
|
|
|
|
| Jarvis's march | computes the convex hull of a set Q of points by a technique known as package wrapping (or gift wrapping).
(See page 955)
|
|
|
|
| right chain | When the highest vertex is reached, say pk (breaking ties by choosing the farthest such vertex), we have constructed the right chain of CH(Q).
(See page 955)
|
|
|
|
| left chain | start at pk and choose pk+1 as the point with the smallest polar angle with respect to pk, but from the negative x-axis. Continue on, forming the left chain by taking polar angles from the negative x-axis, until the chain comes back to the original vertex p0.
(See page 955)
|
|
|
|
| star-shaped | A polygon P is star-shaped if there exists a point p in the interior of P that is in the shadow of every point on the boundary of P.
(See page 957)
|
|
|
|
| kernel | the set of all points p in the interior of a star-shaped polygon P, that are in the shadow of every point on the boundary of P.
(See page 957)
|
|
|
|
| on-line convex-hull problem | Given the set Q of n points one point at a time. After receiving each point, compute the convex hull of the points seen so far.
(See page 957)
|
|
|
|
| L(sub m)-distance | The distance between two points can be defined in ways other than euclidean. In the plane, the Lm-distance between points p1 and p2 is given by the expression (|x1 - x2|m + |y1 - y2|m)1/m.
(See page 962)
|
|
|
|
| dominates | Let Q be a set of n points in the plane. Point (x, y) dominates point
(x′, y′) if x ≥ x′ and y ≥ y′.
(See page 962)
|
|
|
|
| maximal | A point in Q that is dominated by no other points in Q.
(See page 962)
|
|
|
|
| maximal layers | Q may contain many maximal points, which can be organized into maximal layers. The first maximal layer L1 is the set of maximal points of Q.
(See page 962)
|
2002 McGraw-Hill Higher Education