Question 5. (15 points) Drawing a tree In this problem, we want to draw a complete binary tree in 2-D, but with the restriction that we are already given the points in the plane that we can choose as vertices for the tree. We are given a set of n points {p} = (xi,y)}}=1 ER2 and a complete binary tree T. We want to map each vertex of the tree to exactly one of these points in such a manner that when we draw the edges of the tree, no two edges should intersect at any point, except at a vertex. Give an algorithm which gives us the mapping of vertices to points in O(n log?n). Hint 5.1. If we have a complete binary tree, then we have a root vertex. Find the point p; to which we can map the root vertex and which lets us partition the remaining points based on some measure. We want to use divide and conquer to solve this problem. Note 5.1. We cannot choose the left most point as the root and divide the remaining points based on y coordinate, e.g. in fig. 1 we see that there are two edges which intersect. HW 2 4 Figure 1: Drawing based on left most point en 3 2 7 Similarly choosing the middle point as the root does not work as we can no longer apply the same algorithm on the left and right sides because we don't want edges to intersect. Instead think of sorting based on angle. Question 5. (15 points) Drawing a tree In this problem, we want to draw a complete binary tree in 2-D, but with the restriction that we are already given the points in the plane that we can choose as vertices for the tree. We are given a set of n points {p} = (xi,y)}}=1 ER2 and a complete binary tree T. We want to map each vertex of the tree to exactly one of these points in such a manner that when we draw the edges of the tree, no two edges should intersect at any point, except at a vertex. Give an algorithm which gives us the mapping of vertices to points in O(n log?n). Hint 5.1. If we have a complete binary tree, then we have a root vertex. Find the point p; to which we can map the root vertex and which lets us partition the remaining points based on some measure. We want to use divide and conquer to solve this problem. Note 5.1. We cannot choose the left most point as the root and divide the remaining points based on y coordinate, e.g. in fig. 1 we see that there are two edges which intersect. HW 2 4 Figure 1: Drawing based on left most point en 3 2 7 Similarly choosing the middle point as the root does not work as we can no longer apply the same algorithm on the left and right sides because we don't want edges to intersect. Instead think of sorting based on angle
