  We propose a novel technique, termed compact shape trees, for computing
correspondences of single-boundary 2-D shapes in O(n2) time. Together with zero
or more features defined at each of n sample points on the shape's boundary,
the compact shape tree of a shape comprises the O(n) collection of vectors
emanating from any of the sample points on the shape's boundary to the rest of
the sample points on the boundary. As it turns out, compact shape trees have a
number of elegant properties both in the spatial and frequency domains. In
particular, via a simple vector-algebraic argument, we show that the O(n)
collection of vectors in a compact shape tree possesses at least the same
discriminatory power as the O(n2) collection of lines emanating from each
sample point to every other sample point on a shape's boundary. In addition, we
describe neat approaches for achieving scale and rotation invariance with
compact shape trees in the spatial domain; by viewing compact shape trees as
aperiodic discrete signals, we also prove scale and rotation invariance
properties for them in the Fourier domain. Towards these, along the way, using
concepts from differential geometry and the Calculus, we propose a novel theory
for sampling 2-D shape boundaries in a scale and rotation invariant manner.
Finally, we propose a number of shape recognition experiments to test the
efficacy of our concept.
