  The goal of the \emph{alignment problem} is to align a (given) point cloud $P
= \{p_1,\cdots,p_n\}$ to another (observed) point cloud $Q =
\{q_1,\cdots,q_n\}$. That is, to compute a rotation matrix $R \in \mathbb{R}^{3
\times 3}$ and a translation vector $t \in \mathbb{R}^{3}$ that minimize the
sum of paired distances $\sum_{i=1}^n D(Rp_i-t,q_i)$ for some distance function
$D$. A harder version is the \emph{registration problem}, where the
correspondence is unknown, and the minimum is also over all possible
correspondence functions from $P$ to $Q$. Heuristics such as the Iterative
Closest Point (ICP) algorithm and its variants were suggested for these
problems, but none yield a provable non-trivial approximation for the global
optimum.
  We prove that there \emph{always} exists a "witness" set of $3$ pairs in $P
\times Q$ that, via novel alignment algorithm, defines a constant factor
approximation (in the worst case) to this global optimum. We then provide
algorithms that recover this witness set and yield the first provable constant
factor approximation for the: (i) alignment problem in $O(n)$ expected time,
and (ii) registration problem in polynomial time. Such small witness sets exist
for many variants including points in $d$-dimensional space, outlier-resistant
cost functions, and different correspondence types.
  Extensive experimental results on real and synthetic datasets show that our
approximation constants are, in practice, close to $1$, and up to x$10$ times
smaller than state-of-the-art algorithms.
