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. (The cells of the diagram should continue outside the square, not stopping at the square's boundaries.)
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.
For 266 students, based on the graduate reading:
For the additively-weighted Voronoi diagrams used in the reading, for the Euclidean plane, the boundary between the cells for two sites with unequal weight is part of a hyperbola. If those are the only two sites, one of them will have a convex cell while the other cell will be star-shaped but not convex. Describe how to determine, by comparing the weights of the two sites, which of the two sites will have the convex cell.
Based on part (a), prove that for an additively-weighted Voronoi diagram with more than two sites, at least one of the sites will have a convex cell. (Hint: an intersection of convex sets is convex, and the cell for any site is the intersection of its cells in all possible two-site diagrams with the other sites.)