Title CSE321/CSE326 - Additional notes on divide and conquer geometry problems ✅

Partitioning Y in linear time Q1) Is this even needed? Yes, because otherwise the total complexity will not be O(n log n). If we don't partition Y when making the recursive calls, each subproblem will have to iterate over an array that has all points in order to get Y’. In this case, the target recurrence won’t apply anymore, and the cost can get to quadratic.(You can verify by analysis). Q2) How to get YL and YR efficiently? Recall that this needs to be done in linear time. Easy solution: loop over Y in order, and for points that are on the left of the dividing line, add them to YL, and the points that are on the right, add them to YR. Detecting whether a point is on the left or the right is straightforward. However, this does not consider the points that are on the dividing line. Why does this need to be done carefully? The points that are on the line need to be assigned in the same way they were partitioned when X was divided. The above mechanism does not guarantee that. Solutions? - Add an attribute to the Point class that stores whether a point was assigned left or right. Set this attribute when XL and XR are created. This will be just used during the partitioning time, and will be overridden in the recursive calls without problem. - Exercise: Other solutions without additional linear space? - While sorting points by x at the beginning, let the comparator sort by y, if the points have equal x. Point[] X= Arrays.sort(list, /* a comparator that sorts points by x then y if there is a tie */); - When dividing points by x, count the number of points in XL that are on the dividing line. These will be the last points in the XL array. Note that this can be done in less than linear time. Let the count be m. - While partitioning Y, the points on the dividing line that were assigned to the left will appear before the other points with the same x dimension. Add the first m of such points to YL. - Note that partitioning Y can all be done in the same loop. No need to make another loop for this.