A tree-edit-distance algorithm for comparing simple, closed shapes

Abstract

A b s t r a c t We discuss a graph-algorithmic approach to comparing shapes. We focus in this paper on comparing simple closed curves in the plane. Our approach is to (1) represent such a shape by its skeleton, which is a tree embedded in the plane, and (2) compare two shapes by comparing their skeletons via tree edit-distance. In this paper, we define our version of tree edit-distance (it differs from that previously described in the literature), and give a polynomial-time algorithm to compute the distance between two trees.