Nearly Optimal Coverings of Orientation Space

Charles F. F. Karney ([email protected])
Version 1.0, March 6, 2006
Version 1.1 (with minor revisions), October 12, 2015

Introduction

Here we give various sets of orientations which cover orientation space nearly optimally. These are suitable for searching orientation space and for integrating over orientation (together with the provided weights). The background to this work is given in Section 8 of

Charles F. F. Karney,
Quaternions in molecular modeling,
J. Mol. Graph. Mod. 25(5), 595–604 (Jan. 2007),
Preprint: arXiv:physics/0506177.

Given a set of N orientations, we define its covering radius, α, as the maximum amount by which an arbitrary orientation needs to be rotated to align it with the closest member of the set. The coverage, c, is defined as

c = N(α − sin α)/π

A set of orientations is optimal if

• there are no other sets with the same number of elements with a smaller α (and c).
• all sets with a smaller number of elements have a larger α.

For any set of N orientations, we can perform a Voronoi tessellation of orientation space, associating with each member of the set, q_i, all orientations for which q_i is the closest orientation. We define the relative weight of q_i as

w_i = N (volume of Voronoi cell i ) / (volume of orientation space)

We can approximate an orientational average of f (q) with

⟨f ⟩ = ∑_i w_i f (q_i) / N

Assuming that the variation in f is bounded, we expect that, for a given N, the error in this approximation to be minimized with an optimal set of orientations.

Expressing the orientation as a unit quaternion or a pair of opposite points on S³, we see that this problem is just a 4-dimensional generalization of the “spherical covering” problem. See

R. H. Hardin, N. J. A. Sloane, and W. D. Smith,
Spherical coverings, (Feb. 1984),

with the additional constraint that the points come as opposite pairs. The formula for c above involves the “area” of a spherical cap on S³ of radius α/2. A quaternion [q₀, q₁, q₂, q₃] represents the rotation give by the matrix whose components are

1 − 2q22 − 2q32	2q1q2 − 2q0q3	2q1q3 + 2q0q2
2q2q1 + 2q0q3	1 − 2q32 − 2q12	2q2q3 − 2q0q1
2q3q1 − 2q0q2	2q3q2 + 2q0q1	1 − 2q12 − 2q22

where we have assumed that the quaternion is normalized, i.e., q₀² + q₁² + q₂² + q₃² = 1.

The problem of determining good orientation sets for the purposes of averaging is discussed in

M. Edén and M. H. Levitt,
Computation of orientational averages in solid state NMR by Gaussian spherical quadrature,
J. Magn. Reson. 132, 220–239 (1998).

Table of orientation sets

Because determining optimal sets of points is a hard problem, we provide here “nearly” optimal sets of points. We begin by providing a table of the orientation sets ranked by decreasing α.

name	N	α (°)	c	δ	σ	download
c48u1	24	62.80	1.57514	0.70000	0.00	quat grid euler
c600v	60	44.48	1.44480			quat euler
c48u9	216	38.45	3.38698	0.41422	0.00	quat grid euler
c48n9	216	36.47	2.89689	0.26091	7.00	quat grid euler
c600vc	360	27.78	2.15246			quat euler
c600vec	720	22.25	2.22117			quat euler
c48u27	648	20.83	1.64091	0.33582	0.00	quat grid euler
c48u83	1992	16.29	2.42065	0.25970	0.00	quat grid euler
c48u157	3768	14.49	3.22614	0.20710	0.00	quat grid euler
c48u181	4344	12.29	2.27013	0.19415	0.00	quat grid euler
c48u309	7416	10.07	2.13338	0.15846	0.00	quat grid euler
c48n309	7416	9.72	1.91567	0.15167	1.86	quat grid euler
c48u519	12456	9.05	2.60257	0.13807	0.00	quat grid
c48u527	12648	8.43	2.13318	0.13229	0.00	quat grid
c48n527	12648	8.17	1.94334	0.12599	1.86	quat grid
c48u815	19560	7.40	2.23719	0.11607	0.00	quat grid
c48u1153	27672	6.60	2.23735	0.10330	0.00	quat grid
c48u1201	28824	6.48	2.20918	0.09999	0.00	quat grid
c48u1641	39384	5.75	2.10646	0.08993	0.00	quat grid
c48u2219	53256	5.27	2.20117	0.08249	0.00	quat grid
c48u2867	68808	5.24	2.79649	0.07531	0.00	quat grid
c48u2947	70728	4.71	2.07843	0.07359	0.00	quat grid
c48u3733	89592	4.37	2.11197	0.06836	0.00	quat grid
c48u4701	112824	4.22	2.39041	0.06372	0.00	quat grid
c48u4749	113976	4.00	2.05300	0.06248	0.00	quat grid
c48u5879	141096	3.74	2.07325	0.05837	0.00	quat grid
c48u7111	170664	3.53	2.11481	0.05514	0.00	quat grid
c48u8649	207576	3.26	2.02898	0.05094	0.00	quat grid

The orientation sets can be downloaded by the links in the “download” column. The “quat” and “euler” files are in the following format:

• Any number of initial comment lines beginning with “#”.
• A line containing either “format quaternion” or “format euler”.
• A line containing: N α(°) c.
• N lines containing: q_0i q_1i q_2i q_3i w_i (for quaternions)
• or N lines containing: a_i b_i g_i w_i (for Euler angles).

The convention for Euler angles is that the rotation is given by R_z(a) R_y(b) R_z(g).

The “grid” links provide a compact representation for those orientation sets based on the 48-cell with δ and σ determining the grid spacing. This is described below. Only a subset of orientations sets in Euler angle format is provided here.

The following orientation sets are non-optimal:

• c48u9 (beaten by c48n9),
• c600vec (beaten by c48u27),
• c48u309 (beaten by c48n309),
• c48u527 (beaten by c48n527).

The following orientation sets are sub-optimal with a substantially thinner covering achieved by another set with somewhat more points:

• c48u157 (use c48u181 instead),
• c48u519 (use c48n527 instead),
• c48u2867 (use c48u2947 instead),
• c48u4701 (use c48u4749 instead).

Sets based on regular and semi-regular polytopes

One strategy for evenly spacing points on S³ is to place the points using the vertices or cell centers of regular and semi-regular polytopes. The vertices of all the regular 4-dimensional polytopes is given in

http://paulbourke.net/geometry/hyperspace/

c48u1 and c660v are two such sets. The points in c48u1 are placed at the centers of the cells of a truncated-cubic tetracontoctachoron (48-cell), see

https://en.wikipedia.org/wiki/Tetracontoctachoron.

These points are obtained by using the vertices of 2 24-cells in their mutually dual positions. Similarly the points in c600v are the vertices of a 600-cell. Both c48u1 and c600v probably are optimal sets.

The set c600v can be extended by adding the centers of the cells of the 600-cell (equivalent to the vertices of its dual, the 120-cell) to give the set c600vc and by adding, in addition, the midpoints of the edges of the 600-cell, to give the set c600vec.

Sets based on gridding the 48-cell

In order to obtain larger sets we seek a systematic way to place multiple points with the cells of a polytope. The 48-cell is convenient for this purpose. The cells are all identical truncated cubes and thus a body-center-cubic lattice lines up nicely with the cells. [A body-center-cubic lattice provides the thinnest covering of R³; see R. P. Bambah, On lattice coverings by spheres, Proc. Nat. Inst. Sci. India 20, 25–52 (1954).]

Here is the procedure. Each cell of the 48-cell is a truncated cube. Define the primary cell as

p₀ = 1,
p_i>0 < √2 − 1,
|p₁| + |p₂| + |p₃| < 1.

The other cells are generated from this by the application of the rotational symmetry group of the cube.

Place a body-centered-cubic lattice, with lattice spacing δ, within the primary cell (including only points lying within the cell). Thus we take

p₀ = 1,
[p₁, p₂, p₃] = [k, l, m] δ/2

where [k, l, m] are either all even or all odd integers (to give a BCC lattice). These points are then normalized with q = p/|p| to place them on S³.

As δ is varied the number of points within the cell (N/24) varies. For a given N, pick the δ with the smallest covering. (To obtain the sets given here, we systematically varied δ in steps of 0.00001.) Discard any N for which there is a smaller N with a smaller (or equal) α.

This procedure yields the sets c48uMMM where MMM = N_c = N/24 is the number of points per cell.

There are many ways in which we might imagine improving these sets. One possibility is to use a non-uniform lattice spacing using

p₁ = sinh(σ k δ/2)/σ,

and similarly for p₂ and p₃. (The uniform lattice is recovered in the limit σ → 0.) The increasing lattice spacing afforded by the sinh function counteracts the bunching of points occurring when the lattice points are projected onto S³.) The two sets c48n309 and c48n527 are two examples with reasonably thin coverage. In the case of c48n9, σ is used merely to delay the entry of a new set of points into the primary cell.

One might also offset the lattice and remove or perturb the points near the surface of the cells. However because these strategies make the search for good sets considerably more complex, the simple procedure with the uniform lattice outlined above probably suffices for most purposes.

Because of the regular way that the grids are obtained, we can define a compact represtentation of the orientation set with a file in the “grid” format. This consists of

• Any number of initial comment lines beginning with “#”.
• A line containing “format grid”.
• A line containing: δ σ N N_c N_d α(°) c.
• N_d lines containing: k_i l_i m_i w_i r_i(°) M_i.

where N_d is the number of distinct entries, r_i is the radius of the i th Voronoi cell [thus α = max_i(r_i)], and M_i is the multiplicity of the entry. In the file, we restrict k_i ≥ l_i ≥ m_i ≥ 0. For each such [k_i, l_i, m_i], we generate M_i distinct permutations by changing the order and the signs of the elements.

Code to produce the full orientation sets for the grid form is available in ExpandSet.cpp. After compiling this code, you can generate a quaternion orientation set with, e.g.,

./ExpandSet < c48u527.grid > c48u527.quat

Supply the “-e” option to obtain the corresponding file of Euler angles.

Additional denser orientation sets are provided below. Because these sets contain a large number of orientations (up to 25×10⁶), they are provided only the grid format.

Further remarks

For each set, can obtain new sets by performing an arbitrary rotation of R⁴ via

q_i′ = r q_i s,

where r and s are fixed (possibly random) unit quaternions. The pre- and post-multiplication allows all rotations of R⁴ to be accessed.

One way of estimating the error in the numerical quadrature is to repeat the calculation several times with the same set of points but choosing different random r and s each time.

(Note that original sets possess symmetry that if q_i is a member of the set then so is the inverse rotation q_i*. The new sets q_i′ do not have this property, in general.)

Estimated accuracy (ulp = units in last place):

• δ: exact (search for “optimum” was with resolution 10⁻⁵)
• σ: exact
• α: 0.006° (0.6 ulp)
• c: 0.6×10⁻⁵ (0.6 ulp)
• w: average 1.5×10⁻⁶ (1 ulp), maximum 4×10⁻⁶ (4 ulp) (last digit adjusted to give ∑_i w_i = N)
• r: 0.015° (1.5 ulp)
• q₀, q₁, q₂, q₃: 0.51×10⁻⁹ (0.51 ulp)

ZCW3 Orientation Sets

Edén and Levitt studied the ZCW3 orientation sets. These are based on gridding the space of Euler angles. These yield less thin coverings of orientation space that the sets given above. Here is the data

name	N	α (°)	c
ZCW3_50	50	69.66	4.426
ZCW3_100	100	56.05	4.735
ZCW3_144	144	42.44	3.021
ZCW3_200	200	48.07	6.050
ZCW3_300	300	40.25	5.384
ZCW3_538	538	32.53	5.142
ZCW3_1154	1154	26.81	6.203
ZCW3_3722	3722	18.33	6.436
ZCW3_6044	6044	18.10	10.051

Denser orientation sets

The procedure used to obtain the orientation sets based on the 48-cell can be continued to obtain denser orientation sets. Here are the results for uniform grids (σ = 0):

name	N	α (°)	c	δ	approx δ	download
	141096	3.735	2.07261	0.058364	2/34.2973
	170664	3.529	2.11458	0.055138	2/36.2973
	207576	3.260	2.02803	0.050932	2s/16.2657
c48u10305	247320	3.102	2.08130	0.048456	2/41.2973	grid
c48u12083	289992	3.096	2.42678	0.046023		grid
c48u12251	294024	2.903	2.02950	0.045354	2s/18.2657	grid
c48u14251	342024	2.767	2.04269	0.043215	2/46.2973	grid
c48u16533	396792	2.655	2.09385	0.041421	2/48.2973	grid
c48u19181	460344	2.497	2.02149	0.039000	2s/21.2450	grid
c48u21863	524712	2.403	2.05419	0.037534	2/53.2973	grid
c48u25039	600936	2.282	2.01458	0.035641	2s/23.2450	grid
c48u28329	679896	2.197	2.03407	0.034313	2/58.2973	grid
c48u31793	763032	2.162	2.17361	0.033137		grid
c48u32081	769944	2.116	2.05852	0.032786		grid
c48u35851	860424	2.024	2.01113	0.031601	2/63.2973	grid
c48u40003	960072	1.962	2.04420	0.030633	2/65.2973	grid
c48u44709	1073016	1.877	2.00081	0.029307	2s/28.2657	grid
c48u49397	1185528	1.822	2.02304	0.028453	2/70.2973	grid
c48u54799	1315176	1.753	1.99776	0.027370	2s/30.2657	grid
c48u60279	1446696	1.701	2.00892	0.026563	2/75.2973	grid
c48u65985	1583640	1.657	2.03291	0.025876	2/77.2973	grid
c48u72521	1740504	1.596	1.99529	0.024918	2s/33.2450	grid
c48u79099	1898376	1.557	2.01914	0.024303	2/82.2973	grid
c48u86451	2074824	1.505	1.99648	0.023504	2s/35.2450	grid
c48u93701	2248824	1.467	2.00411	0.022911	2/87.2973	grid
c48u101477	2435448	1.447	2.07920	0.022389		grid
c48u101917	2446008	1.444	2.07768	0.022222		grid
c48u110143	2643432	1.388	1.99316	0.021669	2/92.2973	grid
c48u118647	2847528	1.358	2.01352	0.021210	2/94.2973	grid
c48u128249	3077976	1.318	1.98655	0.020574	2s/40.2657	grid
c48u137809	3307416	1.290	2.00301	0.020142	2/99.2973	grid
c48u148395	3561480	1.255	1.98744	0.019600	2s/42.2657	grid
c48u158763	3810312	1.228	1.99130	0.019176	2/104.2973	grid
c48u169757	4074168	1.205	2.01122	0.018815	2/106.2973	grid
c48u181909	4365816	1.173	1.98631	0.018310	2s/45.2450	grid
c48u193767	4650408	1.151	2.00013	0.017970	2/111.2973	grid
c48u207023	4968552	1.123	1.98553	0.017535	2s/47.2450	grid
c48u220121	5282904	1.102	1.99143	0.017197	2/116.2973	grid
c48u233569	5605656	1.083	2.00765	0.016906	2/118.2973	grid
c48u248571	5965704	1.056	1.98203	0.016488	2/121.2973	grid
c48u263339	6320136	1.039	1.99944	0.016221	2/123.2973	grid
c48u279565	6709560	1.015	1.98032	0.015850	2s/52.2657	grid
c48u295333	7087992	0.999	1.99038	0.015589	2/128.2973	grid
c48u312831	7507944	0.978	1.97997	0.015266	2s/54.2657	grid
c48u330023	7920552	0.961	1.98309	0.015004	2/133.2973	grid
c48u347617	8342808	0.947	1.99747	0.014782	2/135.2973	grid
c48u367113	8810712	0.927	1.97956	0.014472	2s/57.2450	grid
c48u386211	9269064	0.913	1.99027	0.014255	2/140.2973	grid
c48u407099	9770376	0.896	1.98011	0.013983	2s/59.2450	grid
c48u427333	10255992	0.882	1.98284	0.013765	2/145.2973	grid
c48u448437	10762488	0.870	1.99711	0.013578	2/147.2973	grid
c48u471503	11316072	0.852	1.97662	0.013307	2/150.2973	grid
c48u493799	11851176	0.841	1.98949	0.013132	2/152.2973	grid
c48u518377	12441048	0.826	1.97564	0.012891	2s/64.2657	grid
c48u542361	13016664	0.814	1.98354	0.012715	2/157.2973	grid
c48u566819	13603656	0.814	2.06674	0.012551		grid
c48u568499	13643976	0.807	2.02337	0.012499		grid
c48u593755	14250120	0.789	1.97681	0.012323	2/162.2973	grid
c48u619981	14879544	0.780	1.98967	0.012173	2/164.2973	grid
c48u648549	15565176	0.766	1.97599	0.011964	2s/69.2450	grid
c48u676103	16226472	0.757	1.98293	0.011813	2/169.2973	grid
c48u706351	16952424	0.747	1.98930	0.011627	2s/71.2450	grid
c48u735777	17658648	0.735	1.97798	0.011475	2/174.2973	grid
c48u765729	18377496	0.727	1.98881	0.011344	2/176.2973	grid
c48u798587	19166088	0.715	1.97265	0.011155	2/179.2973	grid
c48u830491	19931784	0.707	1.98390	0.011032	2/181.2973	grid
c48u865149	20763576	0.696	1.97317	0.010863	2s/76.2657	grid
c48u898517	21564408	0.688	1.97768	0.010735	2/186.2973	grid
c48u932999	22391976	0.683	2.01538	0.010620		grid
c48u970447	23290728	0.670	1.97320	0.010455	2/191.2973	grid
c48u1006449	24154776	0.663	1.98364	0.010347	2/193.2973	grid
c48u1045817	25099608	0.653	1.97289	0.010197	2s/81.2450	grid
c48u1083955	26014920	0.646	1.97878	0.010086	2/198.2973	grid
	27960696	0.630	1.97374	0.009838	2/203.2973
	28943544	0.624	1.98389	0.009742	2/205.2973

As before, ExpandSet.cpp can be used to expand the grids into sets of quaternions or Euler angles. The computation of the weights in these high density grid files is carried out by determining the volume of the Voronoi cells in axis-angle space. Some corrections are applied to account for the fact that orientation space is not flat and the resulting maximum error in the weights is approximately (δ/12)².

The column labeled “approx δ” illustrates that the optimal grid spacing follow one of three patterns (here s = √2 − 1). This follows from the requirement that the separation of the lattice planes at one set of faces (triangles or octogons) be such that the maximum Voronoi radius of points near this face match that of the point at the center of the cell. At the same time, the separation of the lattice planes at the other set of faces must not result in larger Voronoi radii.