Lecture 4 includes the problem of computing the smallest triangle determined by three of \(n\) given points. What about the smallest triangle determined by 3 of \(n\) given lines?
Explain why the smallest triangle determined by 3 of \(n\) lines must be a face of the arrangement. (Hint: Use a proof by contradiction that assumes that the smallest triangle is not a face, and find a smaller triangle.) As a consequence, it can be found in \(O(n^2)\) time by constructing the arrangement and computing the area of each triangular face.
Give an example of an arrangement of four lines, no two of which are parallel, for which the smallest face is not a triangle. Estimate the areas of the faces in your example to show which one is the smallest. (Hints: Your estimates do not need to be exact, as long as you show that the triangular faces are larger than some amount and that some non-triangular face is smaller than the same amount. It may simplify your estimates if you choose two of the lines to be the \(x\)- and \(y\)-axis.)
The DCEL data structure from last week includes five different pointers stored by each half-edge object. One of these pointers is not needed for a DCEL that describes a line arrangement. Which one, and why? (Question was incorrectly phrased; please ignore it.)
If a regular octagon is triangulated, the number of ears can be 2, 3, or 4.
Draw examples of triangulations with each of these numbers of ears.
Explain why a triangulated octagon cannot have five ears.
A convex pentagon has five different triangulations. Which one will be found by the plane sweep algorithm for a regular pentagon with its bottom side horizontal?