The problem of generating uniform deterministic samples over the rotation group, SO(3), is fundamental to computational biology, chemistry, physics, and numerous branches of computer science. We present the best-known method to date for constructing incremental, deterministic grids on SO(3); it provides: (1) the lowest metric distortion for grid neighbor edges, (2) optimal dispersion-reduction with each additional sample, (3) explicit neighborhood structure, and (4) equivolumetric partition of SO(3) by the grid cells. We also demonstrate the use of the sequence on motion planning problems.
Arvo, J. ( 1991). Random rotation matrices. Graphics Gems II, Arvo, J. (ed.). Boston, MA, Academic Press, pp. 355-356.
2.
Arvo, J. ( 1992). Fast Random Rotation Matrices. Boston, MA,Academic Press, pp. 117-120.
3.
Chirikjian, G.S. and Kyatkin, A.B. ( 2001). Engineering Applications of Noncommutative Harmonic Analysis . Boca Raton, FL, CRC Press.
4.
Crowther, R.A. ( 1972). The fast rotation function in the molecular replacement method. Intrumentation Science Review Series, 12: 173-178.
5.
Diaconis, P. and Shahshahani, M. ( 1987). The subgroup algorithm for generating uniform random variables. Probability in Engineering and Information Science , 1: 15-32.
6.
Fishman, G.F. ( 1996). Monte Carlo: Concepts, Algorithms, and Applications. Berlin, Springer.
7.
Górski, K.M., Hivon, E., Banday, A.J., Wandelt, B.D., Hansen, F.K., Reinecke, M. and Bartelmann, M. ( 2005). HEALPix: A framework for high-resolution discretization and fast analysis of data distributed on the sphere. The Astrophysical Journal, 622: 759-771.
8.
Hardin, D.P. and Saff, E.B. ( 2004). Discretizing manifolds via minimum energy points. Notices of the American Mathematical Society, 51(10): 1186-1194.
9.
Jain, S. ( 2009). Library for uniform deterministic sequences/sets of samples over 2-sphere and SO(3). http://www.cs.duke.edu/∼yershova/so3sampling/so3sampling.htm.
10.
Kavraki, L.E., Svestka, P., Latombe, J. and Overmars, M.H. ( 1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12(4): 566-580.
11.
Kuffner, J. ( 2004). Effective sampling and distance metrics for 3D rigid body path planning. IEEE International Conference on Robotics and Automation. Piscataway, NJ, IEEE.
12.
Lindemann, S.R. and LaValle, S.M. ( 2003). Incremental Low-Discrepancy lattice methods for motion planning. IEEE International Conference on Robotics and Automation, pp. 2920-2927.
13.
Lindemann, S.R., Yershova, A. and LaValle, S.M. ( 2004). Incremental grid sampling strategies in robotics. Workshop on the Algorithmic Foundations of Robotics.
14.
Lubotsky, A., Phillips, R. and Sarnak, P. ( 1986). Hecke operators and distributing points on the sphereI. Comments in Pure and Applied Mathamatics, 39: S149-S138.
15.
Mandell, J.G., Roberts, V.A., Pique, M.E., Kotlovyi, V., Mitchell, J.C., Nelson, E., Tsigelny, I. and Ten Eyck, L.F. ( 2001). Protein docking using continuum electrostatics and geometric fit. Protein Engineering, 14(2): 105-113.
16.
Mitchell, J.C. ( 2007). Sampling rotation groups by successive orthogonal images . SIAM Journal on Scientific Computing, 30(1): 525-547.
17.
Niederreiter, H. ( 1992). Random Number Generation and Quasi-Monte-Carlo Methods . Philadelphia, PA, Society for Industrial and Applied Mathematics (SIAM).
18.
Ramamoorthy, S., Rajagopal, R., Ruan, Q. and Wenzel, L. ( 2006). Low-discrepancy curves and efficient coverage of space . Proceedings of the Workshop on Algorithmic Foundations of Robotics.
19.
Rote, G. and Tichy, R.F. ( 1995). Spherical dispersion with applications to polygonal approximation of the curves. Anz. Österreich. Akad. Wiss. Math.-Natur, Kl. Abt. II, 132: 3-10.
20.
Rovira, J., Wonka, P., Castro, F. and Sbert, M. ( 2005). Point sampling with uniformly distributed lines. Point-Based Graphics, 2005. Eurographics/IEEE VGTC Symposium Proceedings.
21.
Saff, E.B. and Kuijlaars, A.B.J. ( 1997). Distributing many points on a sphere. Mathematical Intelligencer, 19(1): 5- 14.
22.
Shoemake, K. ( 1985). Animating rotation with quaternion curves. Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques. New York, ACM Press.
23.
Shoemake, K. ( 1992). Uniform random rotations. Graphics Gems III, Kirk, D. (ed.). Boston, MA, Academic Press, pp. 124-132.
24.
Sloane, N.J.A., Hardin, R.H., Duff, T.D.S. and Conway, J.H. ( 1995). Minimal-energy clusters of hard spheres. Discoveries in Computational Geometry, 14: 237-259.
25.
Sternberg, M.J.E. and Moont, G. ( 2002). Modelling protein- protein and protein-DNA docking. Bioinformatics-From Genomes to Drugs, Lengauer, T. (ed.). Weinheim, Wiley-VCH, pp. 361-404.
26.
Stewart, G.W. ( 1980). The efficient generation of random orthogonal matrices with an application to condition estimation. SIAM Journal on Numerical Analysis, 17(3): 403-409.
27.
Sun, X. and Chen, Z. ( 2008). Spherical basis functions and uniform distribution of points on spheres. Journal of Approximation Theory, 151(2): 186-207.
28.
Wagner, G. ( 1993). On a new method for constructing good point sets on spheres . Journal of Discrete and Computational Geometry, 9(1): 119-129.
29.
Wales, D. and Doye, J. ( 1997). Global optimization by Basin-Hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms. Journal of Physical Chemistry A101, doi:10.1021/jp970984n.
30.
Yan, A.K., Langmead, C.J. and Donald, B.R. ( 2005). A probability-based similarity measure for saupe alignment tensors with applications to residual dipolar couplings in NMR structural biology. The International Journal of Robotics Research, 24(2-3): 162-182.
31.
Yang, G. and Chen, I.-M. ( 2006). Equivolumetric partition of solid spheres with applications to orientation workspace analysis of robot manipulators. IEEE Transactions on Robotics, 22(5): 869-879.
32.
Yershova, A. and LaValle, S.M. ( 2004). Deterministic sampling methods for spheres and SO(3) . Proceedings IEEE International Conference on Robotics and Automation.
33.
Zyczkowski, K. and Kus, M. ( 1994). Random unitary matrices. Journal of Physics A: Mathematical and General, 27(12): 4235-4245.
