- M. Shamos. 1978. Computational geometry.. Abstract: We consider our points in space and generate an “S-coordinate” median hyperplane that will chop this space (and point set) in “half” such that we are left with two regions of space: Pleft defines the points contained entirely to the left of the hyperplane and Pright defines the points entirely to the right of the hyperplane. We can asume that for all points in P, the k-nearest neighbor balls will be generated on each side independently via divide and conquer. Clearly, some such k-nearest neighbor balls will be contained entirely in Pleft or Pright (i.e., does not cross the dividing plane). We know that such balls are correct and should be included in the final solution. Unfortunately, when a ball crosses the dividing plane, the ball may be incorrect. For balls that cross the boundary, there may be a closer k-point on the other side of the plane that was invisible during the divide and conquer step and as such the radius of the ball may need to shrink accordingly. We will need some sort of correction step to correct any such “boundary ball” problems (Figure 1). This correction is a simple point-location problem. Given a collection our collection of balls B in an h-ply system, we want to form a data structure containing our balls such that given a query “q” we can return {Bi : q ∈ Bi} [to our advantage, we know that Bi isn’t too big].
