Computational geometry is the branch of computer science that studies algorithms for solving geometric problems. In modern engineering and mathematics, computational geometry has applications in, among other fields, computer graphics, robotics, VLSI design, computer-aided design, and statistics. The input to a computational-geometry problem is typically a description of a set of geometric objects, such as a set of points, a set of line segments, or the vertices of a polygon in counterclockwise order. The output is often a response to a query about the objects, such as whether any of the lines intersect, or perhaps a new geometric object, such as the convex hull (smallest enclosing convex polygon) of the set of points.

Several of the computational-geometry algorithms in this chapter will require answers to questions about the properties of line segments. A * convex combination* of two distinct points

In this section, we shall explore the following questions:

There are no restrictions on the given points.

Computing cross products is at the heart of our line-segment methods. Consider vectors *p*_{1} and *p*_{2}, shown in Figure 35.1(a). The **cross product***p*_{1} *x* *p*_{2} can be interpreted as the signed area of the parallelogram formed by the points (0, 0), *p*_{1},* p*_{2}, and *p*_{1}* + p*_{2}* = (x*_{1}* + x*_{2},* y*_{1}* + y*_{2)}. An equivalent, but more useful, definition gives the cross product as the determinant of

If *p*_{1}* *X* p*_{2} is positive, then *p*_{1} is clockwise from *p*_{2} with respect to the origin (0, 0); if this cross product is negative, then *p*_{1} is counterclockwise from *p*_{2}. Figure 35.1(b) shows the clockwise and counterclockwise regions relative to a vector *p*. A boundary condition arises if the cross product is zero; in this case, the vectors are * collinear*, pointing in either the same or opposite directions.

(p_{1}- p_{0}) x (p_{2}- p_{0}) = (x_{1 }- x_{0}) (y_{2}- y_{0}) - (x_{2}- x_{0}) (y_{1}- y_{0}).

If this cross product is positive, then is clockwise from ; if negative, it is counterclockwise.

Our next question is whether two consecutive line segments turn left or right at point *p*_{l}.* *Equivalently, we want a method to determine which way a given angle *p*_{0}*p*_{1}*p*_{2} turns. Cross products allow us to answer this question without computing the angle. As shown in Figure 35.2, we simply check whether directed segment is clockwise or counterclockwise relative to directed segment . To do this, we compute the cross product (*p*_{2}* - p*_{0})* *X (*p*_{1}* - p*_{0}). If the sign of this cross product is negative, then is counterclockwise with respect to , and thus we make a left turn at *P*_{1}. A positive cross product indicates a clockwise orientation and a right turn. A cross product of 0 means that points *p*_{0},* p*_{1}, and *p*_{2}* *are collinear*.*

We use a two-stage process to determine whether two line segments intersect. The first stage is * quick rejection*: the line segments cannot intersect if their bounding boxes do not intersect. The

Show how to determine in *0(n*^{2 }1g *n*) time whether any three points in a set of *n* points are collinear.

One way to determine whether a point* p*_{0} is in the interior of a simple, but not necessarily convex, polygon *P* is to look at any ray from *p*_{0} and check that the ray intersects the boundary of *P* an odd number of times but that *p*_{0} itself is not on the boundary of *P*. Show how to compute in (*n*) time whether a point *p*_{0} is in the interior of an *n-*vertex polygon *P. *(*Hint*: Use Exercise 35.1-5. Make sure your algorithm is correct when the ray intersects the polygon boundary at a vertex and when the ray overlaps a side of the polygon.)

Show how to compute the area of an *n-*vertex simple, but not necessarily convex, polygon in (*n*) time.

This section presents an algorithm for determining whether any two line segments in a set of segments intersect. The algorithm uses a technique known as "sweeping," which is common to many computational-geometry algorithms. Moreover, as the exercises at the end of this section show, this algorithm, or simple variations of it, can be used to solve other computational-geometry problems.

In * sweeping*, an imaginary vertical

To be more precise, consider two nonintersecting segments *s*_{1} and *s*_{2 }We say that these segments are * comparable* at

Sweeping algorithms typically manage two sets of data:

1. The * sweep-line status* gives the relationships among the objects intersected by the sweep line.

2. The * event-point schedule* is a sequence of

For some algorithms (the algorithm asked for in Exercise 35.2-7, for example), the event-point schedule is determined dynamically as the algorithm progresses. The algorithm at hand, however, determines the event points statically, based solely on simple properties of the input data. In particular, each segment endpoint is an event point. We sort the segment endpoints by increasing *x*-coordinate and proceed from left to right. We insert a segment into the sweep-line status when its left endpoint is encountered, and we delete it from the sweep-line status when its right endpoint is encountered. Whenever two segments first become consecutive in the total order, we check whether they intersect.

The sweep-line status is a total order *T*, for which we require the following operations:

INSERT(*T,* *s*): insert segment *s* into *T.*

DELETE(*T*, *s*): delete segment *s* from *T.*

ABOVE(*T*, *s*): return the segment immediately above segment *s* in *T.*

BELOW(*T*, *s*): return the segment immediately below segment *s* in *T.*

If there are *n* segments in the input, we can perform each of the above operations in *O(*lg *n)* time using red-black trees. Recall that the red-black-tree operations in Chapter 14 involve comparing keys. We can replace the key comparisons by cross-product comparisons that determine the relative ordering of two segments (see Exercise 35.2-2).

ANY-SEGMENTS-INTERSECT(S)

2 sort the endpoints of the segments inSfrom left to right,

breaking ties by putting points with lowery-coordinates first

3foreach pointpin the sorted list of endpoints

4do ifpis the left endpoint of a segments

5thenINSERT(T,s)

6if(ABOVE(T,s) exists and intersectss)

or (BELOW(T,s) exists and intersectss)

7then returnTRUE

8ifpis the right endpoint of a segments

9then ifboth ABOVE(T,s) and BELOW(T,s) exist

and ABOVE(T,s) intersects BELOW(T,s)

10then returnTRUE

11 DELETE(T,s)

12returnFALSE

The following theorem shows that ANY-SEGMENTS-INTERSECT is correct.

Show that there may be (*n ^{2}*) intersections in a set of

Professor Maginot suggests that we modify ANY-SEGMENTS-INTERSECT so that instead of returning upon finding an intersection, it prints the segments that intersect and continues on to the next iteration of the **for** loop. The professor calls the resulting procedure PRINT-INTERSECTING-SEGMENTs and claims that it prints all intersections, left to right, as they occur in the set of line segments. Show that the professor is wrong on two counts by giving a set of segments for which the first intersection found by PRINT-INTERSECTING-SEGMENTS is not the leftmost one and a set of segments for which PRINT-INTERSECTING-SEGMENTS fails to find all the intersections.

Give an *O*(*n *lg* n*)-time algorithm to determine whether an *n*-vertex polygon is simple.

Give an *O*(*n *lg *n*)-time algorithm to determine whether two simple polygons with a total of *n* vertices intersect.

A * disk* consists of a circle plus its interior and is represented by its center point and radius. Two disks intersect if they have any point in common. Give an

Given a set of *n* line segments containing a total of *k* intersections, show how to output all *k* intersections in *O*((*n + k*) lg *n*) time.

The * convex hull* of a set

There are, in fact, several methods that compute convex hulls in *O*(*n* lg *n*) time. Both Graham's scan and Jarvis's march use a technique called "rotational sweep," processing vertices in the order of the polar angles they form with a reference vertex. Other methods include the following.

In the * incremental method*, the points are sorted from left to right, yielding a sequence <

In the * divide-and-conquer method*, in (

The * prune-and-search method* is similar to the worst-case linear-time median algorithm of Section 10.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. This method is asymptotically the fastest: if the convex hull contains

Computing the convex hull of a set of points is an interesting problem in its own right. Moreover, algorithms for some other computational-geometry problems start by computing a convex hull. Consider, for example, the two-dimensional * farthest-pair problem:* we are given a set of

**Graham's*** scan* solves the convex-hull problem by maintaining a stack

The procedure GRAHAM-SCAN takes as input a set *Q* of points, where |*Q| * 3. It calls the functions TOP(*S*), which returns the point on top of stack *S* without changing *S*, and NEXT-TO-TOP(*S*), which returns the point one entry below the top of stack *S* without changing *S*. As we shall prove in a moment, the stack *S* returned by GRAHAM-SCAN contains, from bottom to top, exactly the vertices of CH(*Q*) in counterclockwise order.

GRAHAM-SCAN(Q)

1 letp_{0}be the point inQwith the minimumy-coordinate,

or the leftmost such point in case of a tie

2 letp_{1},p_{2}, . . . ,pbe the remaining points in_{m}Q,

sorted by polar angle in counterclockwise order aroundp_{0}

(if more than point has the same angle, remove all but

the one that is farthest fromp_{0})

3top[S] 0

4 PUSH(p_{0},S)

5 PUSH(p_{1},S)

6 PUSH(p_{2},S)

7fori3tom

8do whilethe angle formed by points NEXT-TO-TOP(S),

TOP(S), andpmakes a nonleft turn_{i}

9doPOP(S)

10 PUSH(S,p)_{i}

11returnS

The following theorem formally proves the correctness of GRAHAM-SCAN.

We use the aggregate method of amortized analysis to show that the **while** loop takes *O*(*n*) time overall. For *i* = O, 1, . . . , *m*, each point *p _{i}* is pushed onto stack

* Jarvis's march* computes the convex hull of a set Q of points by a technique

More formally, Jarvis's march builds a sequence *H* = *p*_{0}, *p*_{1}, . . . , *p _{h}*-1 of the vertices of CH(

Prove that in the procedure GRAHAM-SCAN, points *p*_{1} and *p _{m}* must be vertices of CH(

Consider a model of computation that supports addition, comparison, and multiplication and for which there is a lower bound of (*n* lg *n*) to sort *n* numbers. Prove that (*n* lg *n*) is a lower bound for computing, in order, the vertices of the convex hull of a set of *n* points in such a model.

For a given polygon *P* and a point *q* on its boundary, the * shadow* of

In the * on-line convex-hull problem*, we are given the set

We now consider the problem of finding the closest pair of points in a set *Q* of *n* 2 points. "Closest" refers to the usual euclidean distance: the distance between points *p*_{1} = (*x*_{1}, *y*_{1}) and *p*_{2} = (*x*_{2}, *y*_{2}) is . Two points in set *Q* may be coincident, in which case the distance between them is zero. This problem has applications in, for example, traffic-control systems. A system for controlling air or sea traffic might need to know which are the two closest vehicles in order to detect potential collisions.

Each recursive invocation of the algorithm takes as input a subset *P* *Q* and arrays *X* and *Y*, each of which contains all the points of the input subset *P*. The points in array *X* are sorted so that their *x*-coordinates are monotonically increasing. Similarly, array *Y* is sorted by monotonically increasing *y*-coordinate. Note that in order to attain the *O*(*n* lg *n*) time bound, we cannot afford to sort in each recursive call; if we did, the recurrence for the running time would be *T*(*n*) = 2*T*(*n*/2) + *O*(*n* lg *n*), whose solution is *T*(*n*) = *O*(*n 1g*^{2 }*n*). We shall see a little later how to use "presorting" to maintain this sorted property without actually sorting in each recursive call.

1length[Y]_{L}length[Y] 0_{R}

2fori1tolength[Y]

3do ifY[i]P_{L}

4thenlength[Y]_{L}length[Y] + 1_{L}

5Y[length[Y]]_{L}Y[i]

6elselength[Y]_{R}length[Y] + 1_{R}

7Y[length[Y]]_{R}Y[i]

The only remaining question is how to get the points sorted in the first place. We do this by simply * presorting* them; that is, we sort them once and for all

Thus, *T*(*n*) = *O*(*n *lg* n*) and *T*'(*n*) = *O*(*n *lg* n*).

The distance between two points can be defined in ways other than euclidean. In the plane, the **L*** _{m}-distance* between points

Given a set *Q* of points in the plane, we define the * convex layers* of

* a*. Give an

Let *Q* be a set of *n* points in the plane. We say that point (*x, y*) * dominates *point (

* a*. Show that

* c*. Describe an

35-4 Sparse-hulled distributions

Consider the problem of computing the convex hull of a set of points in the plane that have been drawn according to some known random distribution. Sometimes, the convex hull of *n* points drawn from such a distribution has *O*(*n*^{1-}) expected size for some constant > 0. We call such a distribution * sparse-hulled*. Sparse-hulled distributions include the following:

Points drawn uniformly from a unit-radius disk. The convex hull has (*n*^{1/3}) expected size.

Points drawn according to a two-dimensional normal distribution. The convex hull has expected size.