Optimal Alignment of 3D Data for Spatial Discretization

We present an algorithm that finds the rotation which best aligns a given configuration of directions on an unsorted set of directions. Using a cost function that we derive in the paper, we show that this algorithm efficiently finds the optimal coordinate frame for a given 3D data set in order to maximize the performance of axis-aligned bounding volumes such as octrees or occupancy grids with regard to the average storage or query cost. The optimization is independent from the initial orientation, since the whole space of rotations is explored. The evaluation becomes computationally feasible by using the Fourier transforms of spherical functions that describe the data as well as the cost function.