Exact solutions

Suppose that all edges in ${\cal G}$ are line segments in ${\mathbb{R}}^m$ for some dimension $m \geq n$. An edge that is generated early in the construction process will be split many times in later iterations. For the purposes of finding the nearest point in $S$, however, it is best to handle this as a single segment. For example, see the three large branches that extend from the root in Figure 5.19. As the number of points increases, the benefit of agglomerating the segments increases. Let each of these agglomerated segments be referred to as a supersegment. To implement NEAREST, a primitive is needed that computes the distance between a point and a line segment. This can be performed in constant time with simple vector calculus. Using this primitive, NEAREST is implemented by iterating over all supersegments and taking the point with minimum distance among all of them. It may be possible to improve performance by building hierarchical data structures that can eliminate large sets of supersegments, but this remains to be seen experimentally.

In some cases, the edges of ${\cal G}$ may not be line segments. For example, the shortest paths between two points in $SO(3)$ are actually circular arcs along ${\mathbb{S}}^3$. One possible solution is to maintain a separate parameterization of ${\cal C}$ for the purposes of computing the NEAREST function. For example, $SO(3)$ can be represented as $[0,1]^3 {/\sim}$, by making the appropriate identifications to obtain ${\mathbb{RP}}^3$. Straight-line segments can then be used. The problem is that the resulting metric is not consistent with the Haar measure, which means that an accidental bias would result. Another option is to tightly enclose ${\mathbb{S}}^3$ in a 4D cube. Every point on ${\mathbb{S}}^3$ can be mapped outward onto a cube face. Due to antipodal identification, only four of the eight cube faces need to be used to obtain a bijection between the set of all rotation and the cube surface. Linear interpolation can be used along the cube faces, as long as both points remain on the same face. If the points are on different faces, then two line segments can be used by bending the shortest path around the corner between the two faces. This scheme will result in less distortion than mapping $SO(3)$ to $[0,1]^3 {/\sim}$; however, some distortion will still exist.

Another approach is to avoid distortion altogether and implement primitives that can compute the distance between a point and a curve. In the case of $SO(3)$, a primitive is needed that can find the distance between a circular arc in ${\mathbb{R}}^m$ and a point in ${\mathbb{R}}^m$. This might not be too difficult, but if the curves are more complicated, then an exact implementation of the NEAREST function may be too expensive computationally.