A Purely Algebraic Justification of the Kabsch-Umeyama Algorithm.

The constrained orthogonal Procrustes problem is the least-squares problem that calls for a rotation matrix that optimally aligns two matrices of the same order. Over past decades, the algorithm of choice for solving this problem has been the Kabsch-Umeyama algorithm, which is effectively no more than the computation of the singular value decomposition of a particular matrix. Its justification, as presented separately by Kabsch and Umeyama, is not totally algebraic since it is based on solving the minimization problem via Lagrange multipliers. In order to provide a more transparent alternative, it is the main purpose of this paper to present a purely algebraic justification of the algorithm through the exclusive use of simple concepts from linear algebra. For the sake of completeness, a proof is also included of the well known and widely used fact that the orientation-preserving rigid motion problem, i.e., the least-squares problem that calls for an orientation-preserving rigid motion that optimally aligns two corresponding sets of points in d-dimensional Euclidean space, reduces to the constrained orthogonal Procrustes problem.

The odd-even invariant and Hamiltonian circuits in tope graphs.

In this paper we consider the question of the existence of Hamiltonian circuits in the tope graphs of central arrangements of hyperplanes. Some of the results describe connections between the existence of Hamiltonian circuits in the arrangement and the odd-even invariant of the arrangement. In conjunction with this, we present some results concerning bounds on the odd-even invariant. The results given here can be formulated more generally for oriented matroids and are still valid in that setting.

Refining the In-Parameter-Order Strategy for Constructing Covering Arrays.

Covering arrays are structures for well-representing extremely large input spaces and are used to efficiently implement blackbox testing for software and hardware. This paper proposes refinements over the In-Parameter-Order strategy (for arbitrary t). When constructing homogeneous-alphabet covering arrays, these refinements reduce runtime in nearly all cases by a factor of more than 5 and in some cases by factors as large as 280. This trend is increasing with the number of columns in the covering array. Moreover, the resulting covering arrays are about 5 % smaller. Consequently, this new algorithm has constructed many covering arrays that are the smallest in the literature. A heuristic variant of the algorithm sometimes produces comparably sized covering arrays while running significantly faster.

Three Rings of Polyhedral Simple Functions.

We survey three ways to multiply elements of the additive subgroup of the group of real-valued functions on R(d) which is generated by the indicator functions of polyhedra. In the resulting commutative rings, identities often correspond to useful techniques of decomposition of polyhedra. We are led immediately to various interesting topics, including Ehrhart polynomials, mixed volumes, Gram's relation, and transversal characteristics.

Cutting the d-Cube.

Some problems concerned with cutting faces of the cube with affine or linear spaces are considered. It is shown that through any d-3 points of R d there passes a hyperplane which cuts all the facets of the d-cube. Furthermore, it is shown that if m < d - 1 and d' < d - [(m + 1)/3], then no m-dimensional affine subspace of R d cuts all the d'-dimensional faces of the cube.