Computing the Relative Neighbour Decomposition of a Simple Polygon

In computational geometry one may be interested in decomposing a polygon into simpler components, monotone polygons for example, in order to solve the geometric problem at hand more efficiently. However, in pattern recognition, where the motivation is morphological, one is interested in decomposing a polygon into perceptually meaningful parts. Therefore we can relax the strict requirement that the components be of a certain form such as convex or monotone and we can investigate decompositions which are procedure oriented rather than component oriented. In this paper we study the properties of a procedure oriented decomposition, termed the relative neighbour decomposition, and present different algorithms for performing such a decomposition.