Consider the "circus tent" example from the lecture notes on 3d convex hulls: \(n/2\) points evenly spaced on a circle on the \(xy\)-plane, and another \(n/2\) points on the positive \(z\)-axis. When the random incremental hull algorithm is run on this example, what is the expected number of points on the \(z\)-axis that, at the time they are processed by the algorithm, lie outside the previously-computed hull and cause a change to the hull? You may use \(O\)-notation in your answer.
Every pentagon is star-shaped, with at least one of its vertices in its kernel.
Explain how to find a vertex in the kernel from a triangulation of a pentagon.
Draw an example of a hexagon that is not star-shaped.
Draw an example of a hexagon that is star-shaped but does not have any of its vertices in the kernel. (Hints: use a triangular kernel, and work backwards from the kernel to the polygon.)
Suppose that we are using Seidel's algorithm to find the biggest circle inside a convex polygon with \(n\) sides, but we are very unlucky and the algorithm calls itself recursively every time it possibly could do so. What is the worst-case running time of the algorithm? Express your answer using \(O\)-notation as a function of \(n\).
Earlier in this class we looked at the problem of computing the smallest area of a triangle determined by three points, from an input of \(n\) points. This problem is not an LP-type problem. Explain why not: which property of LP-type problems does it not have? Give an example demonstrating that it does not have this property.
For 266 students, based on the graduate reading: From the reading, a mesh smoothing method called Laplacian smoothing moves each vertex of a triangle mesh to the centroid of its neighbors, but it has the problem that the result may not even remain a valid triangulation, because it might move a vertex outside the kernel of the polygon formed by its neighbors.
Suppose we try to modify Laplacian smoothing by moving each vertex (one at a time) to the point that belongs to the kernel of the polygon formed by its neighbors and that, among points in the kernel, is the closest to the centroid of its neighbors. Explain how to formulate this as a quasiconvex program in the sense described in the reading.
Give a reason why the modification described in part (a) might not be a good choice for mesh smoothing.