A dynamic programming problem regarding closest pair of points. pseudocode and explanation is enough, thank you.

Consider a sct pi,, Pn of 3-dimensional points p (i, yi, zi) and define the distance between two points Pi,Pi to be d(Pi, pi) = V (zi-ri)2 + (Vi-Uj)2 + (2i-Sj)2 Part 1 (15 points) Suppose we sort pi, , pn by x-coordinate and split the set evenly into Q (the first In/2 elements in the sorted list) and R (the remaining [n/2 elements). Let go, qi (resp. r0.r) denote the closest pair of points in Q (resp. R) and let-min { d(r: r) , d(%-%) } denote the minimum distance between these two pairs. Given a point pi - (r,, Vi, , show that there are at most 256 points in the region (Note: You will likely be able to establish a better constant than 256. The key is that the upper bound is O(1). To simplify analysis you may assume that all points have a unique r valuc Part 2 (10 points) Develop an O(n log2n) time algorithm to find the closest pair of distinct points p, and p; minimizing d(p,,pj). You should argue that your algorithm is correct, and prove that the running time is O(n log2 n). Hint: Partition space into cubes of length /2 aligned with the plane separating Q and R and associate cach point p with the corresponding cube containing that point. You may assume the existence of a function labels/2(p) which outputs the index of the cube containing the point p, and you may assume that the cost to query this function is O(1)