Representation of figures by labeled graphs

摘要

Figures of arbitrary shape (not necessarily “thin line”) can be approximated by polygons which are represented as unions of some of their convex subsets. Such representations can be considered as graphs whose nodes correspond to convex subsets and whose branches connect nodes corresponding to intersecting subsets. The nodes of such graphs are labeled with information related to the structure of the convex set they represent. The paper discusses various properties of such graphs including grammars which may generate them. It is also shown that their analysis can provide information about topological properties of the figure and its shape in general.