  A recent paper \cite{CaeCaeSchBar06} proposed a provably optimal, polynomial
time method for performing near-isometric point pattern matching by means of
exact probabilistic inference in a chordal graphical model. Their fundamental
result is that the chordal graph in question is shown to be globally rigid,
implying that exact inference provides the same matching solution as exact
inference in a complete graphical model. This implies that the algorithm is
optimal when there is no noise in the point patterns. In this paper, we present
a new graph which is also globally rigid but has an advantage over the graph
proposed in \cite{CaeCaeSchBar06}: its maximal clique size is smaller,
rendering inference significantly more efficient. However, our graph is not
chordal and thus standard Junction Tree algorithms cannot be directly applied.
Nevertheless, we show that loopy belief propagation in such a graph converges
to the optimal solution. This allows us to retain the optimality guarantee in
the noiseless case, while substantially reducing both memory requirements and
processing time. Our experimental results show that the accuracy of the
proposed solution is indistinguishable from that of \cite{CaeCaeSchBar06} when
there is noise in the point patterns.
