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.