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 uses five pointers per half-edge object, one pointer and two coordinates per vertex object, and a pointer and list object per face object. Some of this information is not needed for a DCEL that describes a line arrangement. Which parts of this data structure can be safely eliminated, and why?
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?
For 266 students, based on the graduate reading: This week's reading shows that, even when a polygon's vertices all have integer coordinates, the optimal solution to the art gallery problem may need to use irrational numbers for the coordinates. As a simpler version of this result, find a hexagon with integer coordinates that can be guarded by a single guard, but only by using a guard with non-integer coordinates.
(Hint: Use a U-shaped region so that the guard can see into both ends of the U, but not from very many points. It is not possible to do this with a pentagon: every pentagon can be guarded from one of its vertices, using the 3-coloring proof of the art gallery theorem, because \(\lfloor\tfrac{5}{3}\rfloor=1\).