These solutions were prepared by Mike Soss.

---

Problem 1

Part (a)

The conjecture is true.

In order to prove the conjecture, assume I don't believe you. I believe that it does some sort of boundary tracing, but I don't believe you that it works perfectly. Then, I really need the following facts to be convinced:

1. The algorithm traces the entire boundary.
2. The algorithm will not get caught in a cycle.
3. The algorithm enters the first pixel the second time in the same way it first entered it. Otherwise we'll trace the boundary twice.

Lemma 1: If P is 4-connected and so is W, then every vertex on the boundary has degree exactly two, meaning that each vertex has exactly two edges adjacent to it.

A vertex cannot have degree 1 or 3, since P and W must lie on different sides of every edge.

Vertices of degree 0.	Vertices of degree 2.	Vertices of degree 4.

Obviously a vertex of degree 0 cannot be on the boundary, so we must show that it is impossible for a vertex of degree 4 to be on the boundary. Suppose there is such a vertex whose neighboring pixels 1 and 3 are black, and 2 and 4 are white. Since P is 4-connected, there must be a path connecting 1 and 3; this path must either enclose 2 or 4. Then the enclosed white pixel is not 4-connected to the outside, and we have a contradiction.

Lemma 2: There is an even number of edges.

Since our points lie on the integer lattice, every edge of our polygon has length 1 in a co-ordinate direction. For every edge we use to move distance 1 to travel in direction d, we have to use an edge to travel in direction -d to complete the cycle.

Now we're ready to prove the conjecture.

Let our polygon be labelled with a clockwise orientation. Then the interior of the polygon is always to the right of the boundary. In other words, if we advance one edge on the polygon, the boundary will be to our right, and the background to our left.

Now we ask, "What happens when the Square-Tracing algorithm crosses an edge?" If the algorithm entered the polygon, then the algorithm moves counterclockwise around one of the vertices. Thus when it crosses the next edge, the interior of the polygon lies to the right of the edge (when looking in the direction of the motion of the algorithm). Thus the algorithm is advancing to the next edge. If the algorithm left the polygon, then the algorithm moves clockwise around one of the vertices. Thus when it crosses the next edge, the background lies to the left of the edge (when looking in the direction of the motion of the algorithm). Thus the algorithm is advancing to the next edge.

Therefore the algorithm is always advancing to the next edge of the polygon, never backtracking, and never skipping an edge. This is crucial to proving that the algorithm does not cycle, because it means that just before the first pixel is entered for the next time, every edge of the polygon has been entered exactly once.

When the first pixel is entered the second time, it must be in the same direction as the first time. This is because the algorithm alternates moving IN the polygon and OUT the polygon with every edge. Since we have an even number of edges, the motion will be the same the second time the algorithm enters an edge.

---

Part (b)

A counterexample:

The path taken by the algorithm is in blue. Note that it only traces the green polygon and misses the inner border. If you want to think of P as a polygon, think of it with two vertices touching.

---

Problem 2

Let P be our polygon, and s be the starting point of the water. Our output will be Q, a queue, the path of the water. Let Y(p) be the function which returns the y co-ordinate of p. Our algorithm is as follows:

---

1. Find TOP and BOTTOM, the two extreme vertices in the y-direction.
   
   
2. Let l₁ = TOP, l₂, ..., l_k = BOTTOM be the left chain of the polygon.
   Let r₁ = TOP, r₂, ..., r_m = BOTTOM be the right chain of the polygon.
   
   
3. i <-- 0; j <-- 0;
   
   
4. while s does not equal BOTTOM (while the water hasn't hit the bottom yet) do
   • if Y(l_i) < Y(r_j) then
     • if [l_i-1,l_i] intersects a downward ray from and including s then the water strikes the edge [l_i-1,l_i].
       • push (Q, the intersection point) // because the water hits the edge
       • push (Q, l_i) // because the water runs down the edge
       • s <-- l_i
     • i <--i + 1
   • else
     • if [r_j-1,r_j] intersects a downward ray from and including s then the water strikes the edge [r_j-1,r_j].
       • push (Q, the intersection point) // because the water hits the edge
       • push (Q, r_j) // because the water runs down the edge
       • s <-- r_j
     • j<-- j + 1

return Q

---

Complexity: Step 1 can be done in linear time (actually, logarithmic). Step 2 is a labelling of O(n) vertices. Step 3 is trivial. Step 4 is a loop, and if s reaches BOTTOM, it is run linearly many times (i or j increases each time), in which each iteration is a constant. The output in Step 5 is linear, since we only add at most two (2) vertices for each iteration of Step 4. Thus the running time (and therefore space) is linear.

Proof of correctness: Every edge is considered for intersection in the order of their lower vertices, and the algorithm finishes in finite time as long as s equals BOTTOM, so it only needs to be proven that

1. Our path Q doesn't cross any edge, and
2. s eventually reaches BOTTOM.

Proof of 1: Suppose that the water path intersects both e_i and e_j. If the path strikes e_i first, then the water runs down e_i to its lower vertex and continues falling from there. If the path is to also strike e_j, then e_j must have some section lower than e_i. Thus e_j's lower vertex must be lower than e_i's lower vertex. Since we are considering edges for intersection in the order of their lower vertices in Step 4, we are guaranteed not to cross an edge.

Proof of 2: Since we don't cross any edges and P is a closed polygon, we will eventually reach BOTTOM.

---

Problem 3

The conjecture is true.

Suppose there were three polygons, P, its first descendant P', and its second descendant P'', such that P and P' are not planar and P'' is. For simplicity, we will assume that P'' lies in the z=0 plane.

Then the z co-ordinate of every vertex of P'' is zero. This implies that the z co-ordinate of every vertex in P' is oscillating around zero, which in turn implies that P' (and thus P and P'') has an even number of vertices. Suppose the z co-ordinate of P'₁ is c. Then the z co-ordinate of P'_i is (-1)ⁱ⁺¹c.

Now we examine the z co-ordinate values of P. (For clarity, I implicitly only discuss the z co-ordinates from now on.) Let P₁ be c-d, with d arbitrary. Then P₂ must be c+d, so that P'₁ is at c. Then P₃ must be at -2c-d, so that P'₂ is at -c. Then P₄ must be at 4c+d, so that P'₃ is at +c, and so on. The absolute value of the coefficient in front of the c is growing exponentially with every next vertex. Eventually it will dominate the expression, meaning that every next vertex is farther away from the z=0 plane. Since P is a cycle (a polygon), this is impossible, as it means that P₁ is closer to z=0 than is P_n, but P_n is closer to z=0 than is P_n+1 = P₁. Contradiction.