Consider a scene with two obstacles, both of which are axis-parallel rectangles that do not intersect each other, and the visibility graph of their eight vertices.
What is the minimum number of edges that this visibility graph can have? Draw two rectangles that achieves this minimum. (Hint: You are not required to place your rectangles in general position. The edges of the rectangles are always included as edges in the visibility graph.)
Find two rectangles whose visibility graph has at least 17 edges.
Find a scene with two obstacles, both of which are axis-parallel rectangles that do not intersect each other, and two additional points \(s\) and \(t\), such that the shortest obstacle-avoiding path from \(s\) to \(t\) starts out from s in a direction that moves directly away from t. (That is, the first edge of this path lies along the line through \(s\) and \(t\), but not on the line segment from \(s\) to \(t\).)
(Hint: For this to be true, \(s\) should be placed on an edge of an obstacle. Arrange the rectangles in such a way that moving away from t allows the path to reach a long diagonal shortcut while moving towards \(t\) would instead force the path to stay nearly axis-parallel.)
Form a quadtree from a unit square with center point \(c\). Subdivide the outer square (forming four squares meeting at \(c\)), and then repeat three times the following step: subdivide the square that has \(c\) as its bottom left corner. The resulting quadtree should have 13 leaf squares (squares that are not subdivided), because you started with one square and each subdivision step increases the number by three. Now, form a balanced quadtree from this quadtree. How many additional subdivision steps does this take? How many leaf squares are in the final balanced quadtree?
Suppose you want to find a mesh with no sharp angles for a convex pentagon with the five vertices \((0,1)\), \((0,n)\), \((n,n)\), \((n,0)\), and \((1,0)\) (an \(n\times n\) square with a small corner near the origin cut off). Give a function of \(n\) such that the optimal number of triangles in this mesh is within a constant factor of your function. (Hints: You could use the integral for the lower bound on the number of triangles, but I think it's easier to just count the squares in a quadtree for this input.)