Let \(A\), \(B\), and \(C\) be three line segments in the plane, without any intersections, and with all six of their endpoints having distinct \(x\)-coordinates.
How many trapezoids are in the trapezoidal decomposition of \(A\), \(B\), and \(C\)? Your answer should not depend on the precise locations of \(A\), \(B\), and \(C\).
What is the largest possible number of trapezoids that can be formed in the history DAG of the trapezoidal decompositions (including the ones that are part of the final decomposition) when \(A\), \(B\), and \(C\) are in positions and an ordering chosen to maximize this number of trapezoids? Give an example of an input and an input ordering that causes this bad behavior.
Draw the Voronoi diagram for five points: the four corners of a square and its center point.
Suppose we want to know the farthest given point from a query point, rather than the closest. Draw the subdivision of the plane resulting from using the locus method for this problem, for the same five points as question 2. Label each of the five points, and label each region of the subdivision by the answer to queries in that region.
If we are doing nearest neighbor queries using a Voronoi diagram, and the query point lies on a vertex or edge of the Voronoi diagram, there is more than one nearest neighbor. One way to answer the query would be to pick only one of those neighbors, arbitrarily. Another possibility would be to list all nearest neighbors. Explain why listing all nearest neighbors cannot always be done in \(O(\log n)\) time per query.