93-82 A Geometric Approach for Denoting and Intersecting TR Subgroups of the Euclidean Group

DIMACS TR: 93-82

A Geometric Approach for Denoting and Intersecting TR Subgroups of the Euclidean Group

Author: Yanxi Liu

ABSTRACT
A group theoretical characterization of surface contacts between solids induces general yet concise expressions for computing relative positions between solids. Whether subgroup intersections can be carried out effectively and efficiently on computers determines whether the group theoretical approach is computationally tractable and thus attractive in practice. Although there are many ways to denote a group and compute group intersections, it is not obvious that there exists a uniform computational denotation for the symmetry groups of surfaces, given the diversity of these groups --- the finite, infinite, discrete and continuous subgroups of the Euclidean group. Furthermore, the denotation we are seeking should also accommodate the computation of group intersections.

In this article a geometric denotation in terms of {\em characteristic invariants} is proposed for an important family of subgroups of the Euclidean group, namely the \TR subgroups, each of which is a semidirect product of a translation subgroup {\bf T} and a rotation subgroup {\bf R} of the Euclidean group. Under this denotation we prove that

\begin{itemize}

\item There exists a one-to-one correspondance between \TR groups and their characteristic invariants;

\item The intersections of \TR groups are closed and can be obtained by some simple geometric calculations on their characteristic invariants;

\item The algorithm for calculating \TR group intersection using characteristic invariants is efficient, i.e.~it has a worst case asymptotic time complexity ${\cal O}(p^2) + {\cal O}\log (\max (a,b))$ where $n$ is the smaller number of isolated distinct rotation axes, if there is any, of the two \TR groups involved in the intersection, and ${\cal O}\log (\max (a,b))$ is time complexity for computing the greatest common divisor for $a$ and $b$. \end{itemize}

These results justify the group theoretic approach to formalizing contacts between solids as being abstractive yet quantitative, general yet computationally tractable. Therefore, the group theoretical formalization of surface contacts is feasible in applications involving transformations between solids in Euclidean space, such as robotics, computer graphics, computer vision and mechanical design.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-82.ps

DIMACS Home Page