33.1 Line-segment properties

33.1-1

Prove that if $p_1 \times p_2$ is positive, then vector $p_1$ is clockwise from vector $p_2$ with respect to the origin $(0, 0)$ and that if this cross product is negative, then $p_1$ is counterclockwise from $p_2$.

(Omit!)

33.1-2

Professor van Pelt proposes that only the $x$-dimension needs to be tested in line 1 of ON-SEGMENT. Show why the professor is wrong.

$(0, 0), (5, 5), (10, 0)$.

33.1-3

The polar angle of a point $p_1$ with respect to an origin point $p_0$ is the angle of the vector $p_1 - p_0$ in the usual polar coordinate system. For example, the polar angle of $(3, 5)$ with respect to $(2, 4)$ is the angle of the vector $(1, 1)$, which is $45$ degrees or $\pi / 4$ radians. The polar angle of $(3, 3)$ with respect to $(2, 4)$ is the angle of the vector $(1, 1)$, which is $315$ degrees or $7\pi / 4$ radians. Write pseudocode to sort a sequence $\langle p_1, p_2, \ldots, p_n \rangle$ of $n$ points according to their polar angles with respect to a given origin point $p_0$. Your procedure should take $O(n\lg n)$ time and use cross products to compare angles.

(Omit!)

33.1-4

Show how to determine in $O(n^2 \lg n)$ time whether any three points in a set of $n$ points are colinear.

Based on exercise 33.1-3, for each point $p_i$, let $p_i$ be $p_0$ and sort other points according to their polar angles mod $\pi$. Then scan linearly to see whether two points have the same polar angle. $O(n \cdot n\lg n) = O(n^2 \lg n)$.

33.1-5

A polygon is a piecewise-linear, closed curve in the plane. That is, it is a curve ending on itself that is formed by a sequence of straight-line segments, called the sides of the polygon. A point joining two consecutive sides is a vertex of the polygon. If the polygon is simple, as we shall generally assume, it does not cross itself. The set of points in the plane enclosed by a simple polygon forms the interior of the polygon, the set of points on the polygon itself forms its boundary, and the set of points surrounding the polygon forms its exterior. 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. A vertex of a convex polygon cannot be expressed as a convex combination of any two distinct points on the boundary or in the interior of the polygon.

Professor Amundsen proposes the following method to determine whether a sequence $\langle p_1, p_2, \ldots, p_{n - 1} \rangle$ of $n$ points forms the consecutive vertices of a convex polygon. Output "yes" if the set ${ \angle p_i p_{i + 1} p_{i + 2}: i = 0, 1, \ldots, n - 1 }$, where subscript addition is performed modulo $n$, does not contain both left turns and right turns; otherwise, output "no." Show that although this method runs in linear time, it does not always produce the correct answer. Modify the professor's method so that it always produces the correct answer in linear time.

A line.

33.1-6

Given a point $p_0 = (x_0, y_0)$, the right horizontal ray from $p_0$ is the set of points ${ p_i = (x_i, y_i) : x_i \ge x_0 ~\text{and}~ y_i = y_0 }$, that is, it is the set of points due right of $p_0$ along with $p_0$ itself. Show how to determine whether a given right horizontal ray from $p_0$ intersects a line segment $\overline{p_1 p_2}$ in $O(1)$ time by reducing the problem to that of determining whether two line segments intersect.

$p_1.y = p_2.y = 0$ and $\max(p_1.x, p_2.x) \ge 0$.

or

$\text{sign}(p_1.y) \ne \text{sign}(p_2.y)$ and \$\displaystyle p_1.y \cdot \frac{p_1.x - p_2.x}{p_1.y - p_2.y} \ge 0{equation}

33.1-7

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 $\Theta(n)$ time whether a point $p_0$ is in the interior of an $n$-vertex polygon $P$. (Hint: Use Exercise 33.1-6. 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.)

Based on exercise 33.1-6, use $p_i - p_0$ as $p_i$.

33.1-8

Show how to compute the area of an $n$-vertex simple, but not necessarily convex, polygon in $\Theta(n)$ time. (See Exercise 33.1-5 for definitions pertaining to polygons.)

Half of the sum of the cross products of ${\overline{p_1 p_i}, \overline{p_1 p_{i + 1}} ~|~ i \in [2, n - 1] }$.