CS 164/266, Fall 2023, Practice Problem Set 1

Suppose we apply the Graham scan algorithm (twice) to find the upper and lower hulls of a set of five points in the plane, with no two of the points having the same $x$ -coordinate and no three in a line. For which pairs of numbers $(u, ℓ)$ is it possible that the algorithm performs exactly $u$ pop operations while computing the upper hull, and exactly $ℓ$ operations while computing the lower hull? For each of these pairs, draw an example of a set of points for which the algorithm performs that many pop operations.
Suppose that we are given two points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ and we wish to test whether they are on opposite sides of the line $a x + b y + c = 0$ .
1. Describe how to test this, using the dot products of three triples of numbers: the triples $(x_{1}, y_{1}, 1)$ and $(x_{2}, y_{2}, 1)$ obtained by converting the points to projective coordinates, and the triple $(a, b, c)$ of projective coordinates of the line. Your description may either be in English or pseudocode.
2. Suppose we apply the same test to a different set of three triples of numbers. We replace the coordinates of the two points by the triples $(a_{1}, b_{1}, c_{1})$ and $(a_{2}, b_{2}, c_{2})$ describing two lines, and we replace the coordinate of the line by a triple $(x, y, 1)$ describing a point. For a given pair of lines $(a_{1}, b_{1}, c_{1})$ and $(a_{2}, b_{2}, c_{2})$ , describe the shape formed by the points $(x, y, 1)$ for which the test returns true.
In the plane sweep algorithm for listing all crossings, we made the simplifying “general position” assumption that at most two line segments cross at any point. Suppose that exactly three line segments cross at some point during the algorithm. How would the vertical ordering of the segments change at that crossing?
Form a triangle from three points (not all in a line) by connecting them with three line segments.
1. How many objects of each of the three types (half-edge, vertex, and face) are there in a doubly-connected edge list that represents the arrangement of these three line segments?
2. Label these objects by letters and draw the triangle with your labels placed on it to show which label goes with which object.
3. Use these labels to describe, for each half-edge, the five pointers stored by that half-edge. For instance, if half-edge $a$ has a twin half-edge $b$ , comes from vertex $v$ , has face $f$ on its side of its edge, and has half-edges $c$ and $d$ as its next and previous half-edges on face $f$ , you could describe it by writing $a : b v f c d$ .