Homework 2

“Oh, he seems like an okay person, except for being a little strange in some ways. All day he sits at his desk and scribbles, scribbles, scribbles. Then, at the end of the day, he takes the sheets of paper he’s scribbled on, scrunges them all up, and throws them in the trash can.”
– John von Neumann’s housekeeper, describing the employer

This HW is due on 20th February 2025. Please write down the solutions neatly in your own handwriting, and submit the completed HW by email by the beginning of class on 20th February 2025. Please submit the HW as a single pdf file - you can scan / take a photo of your completed HW (handwritten) and convert it into a pdf file (please name your file first.last_hw2.pdf). To get credit, please provide all details and give complete reasoning for all your work. Do not consult any books, internet resources or AI. If you have questions about the problems, we can discuss them in class.

Exercise 1 (2 points) Let C_1, \cdots, C_n be n convex subsets of \mathbb{R}^2. Prove that C_1 \cap \cdots \cap C_n is also a convex subset of \mathbb{R}^2.

Exercise 2 (2 points) Let S =\{s_1,\cdots, s_n\} be a finite set of points in \mathbb{R}^2. Give a complete proof of the fact that the Voronoi region \textbf{Vor} (s_i) corresponding to each s_i is a convex subset of \mathbb{R}^2.

Exercise 3 (4 points) Let S = \{A(0, 0),B(5,−1),C(7,−5),D(9, 4),E(3, 9)\} \subset \mathbb{R}^2.

  1. Construct the triangulations \mathcal{T}_v and \mathcal{T}_h of S using vertical line sweep from left to right and the horizontal line sweep upwards.

  2. We can get the Delaunay triangulation on S by doing edge flips. Show the edge flips necessary to produce a Delaunay triangulation from \mathcal{T}_v? From \mathcal{T}_h?

  3. Draw the corresponding Voronoi diagrams in each case above. Is it the same diagram for both cases?

Exercise 4 (2 points) From the examples we saw in class, it seems that if we introduce an extra point (“site”) in an existing Voronoi diagram, the changes of the existing diagram are only “local”, i.e. affects only a few neighboring regions. Is it possible to find a configuaration of N sites (for any N, however large) such that the resultant Voronoi diagram is such that every Voronoi region is changed by addition of some single new site? If such a configuration is possible, sketch such an example for N=8 and show that adding some new site changes the Voronoi region of each of the previous N sites.