## 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