Extension to Higher Dimensions

CircularTrip can be immediately extended to a higher dimensional space. Take $3$ D space for example. The only difference is now CircularTrip (Algorithm ) returns the cells intersected by the sphere of radius $r$ centered at $q$ . Given a query $q(x, y, z)$ , CircularTrip is invoked on the plane $z = \lfloor p.z / \delta \rfloor$ and its results is $C$ . Then, for each pair of cells in $C$ intersected by the planes parallel to the plane $y = \lfloor p.y / \delta \rfloor$ , call CircularTrip with one of them as $c_{start}$ and half of their distance as radius to collect all the satisfied cells. It is immediately verified that properties of CircularTrip in 2D are all retained.

Figure: Minimum Angular Distance