CS 164/266, Fall 2023, Practice Problem Set 6

Consider a point set $S$ consisting of $2 n$ points: $n$ points on the $x$ -axis with coordinates $(x, 0)$ for $x = 1, 2, \dots, n$ , and $n$ more points on the $y$ -axis with coordinates $(0, y)$ for $y = n + 1, n + 2, \dots, 2 n$ . For the purpose of the following questions, a circle "passes through" a point if the distance of the point from the center is equal to the radius of the circle. The circle "encloses" a point if the distance of the point from the center is strictly less than the radius of the circle.
1. Let $C_{i}$ be the largest circle that passes through two consecutive $x$ -axis points $(i, 0)$ and $(i + 1, 0)$ , but that does not enclose any integer points on either axis (regardless of whether these points are in $S$ or not). Then circle $C_{i}$ will also pass through two integer points on the $y$ -axis. What are the coordinates of these two points?
  
  (Hint: Use symmetry across a diagonal axis.)
2. Let $D_{i}$ be the largest circle that passes through two consecutive $x$ -axis points $(i, 0)$ and $(i + 1, 0)$ , but that does not enclose any points of $S$ . Then circle $D_{i}$ will also pass through a point of $S$ on the $y$ -axis. What are the coordinates of this point?
  
  (Hint: start with circle $C_{i}$ and then grow it, with the growing circle continuing to pass through $(i, 0)$ and $(i + 1, 0)$ ; for examples of this growth pattern see slide "Why is this a triangulation?" of the Delaunay triangulation lecture notes.)
3. Based on the result of part (b), which pairs of points form edges of the Delaunay triangulation of these $2 n$ points?
4. Use part (c) and the idea from the "circus tent" 3d convex hull example to find an order for inserting these $2 n$ points into a Delaunay triangulation, starting with the three vertices of their convex hull, that would cause the flipping algorithm to make a number of flips that is proportional to $n^{2}$ .
The minimum spanning tree of a set of $n$ points always has the following property: each point has an edge connecting it to its nearest neighbor in the set.
1. Find an example of a set of four points for which connecting every point to its nearest neighbor produces all of the edges in the minimum spanning tree.
2. Find an example of a set of four points for which connecting every point to its nearest neighbor does not produce all of the edges in the minimum spanning tree.
Draw the subdivision of the plane resulting from an autopartition of the arrangement of three line segments shown below. You may choose any segment ordering for the autopartition; you do not have to order them randomly. Label each region of the resulting subdivision, and draw a binary tree representing the binary space partition, with the leaf nodes of the tree labeled by their corresponding regions.

(If you redraw the segments rather than copying this image, you do not need them to be in precisely the same geometric positions as long as it does not affect the structure of the binary space partition.)
For the same arrangement, draw the subdivision of the plane resulting from the shallow partition strategy, starting with an initial slab whose top and bottom lines pass through the top and bottom vertices of the arrangement. If this strategy needs to choose a median of an even number of items, choose the smaller of the two median values. Label each region of the resulting subdivision, and draw a binary tree representing the binary space partition, with the leaf nodes of the tree labeled by their corresponding regions.