Finding convex deficiencies in linear time

A new algorithm for obtaining the convex deficiencies of an arbitrary 8-connected digital figure in linear time and space is presented. It is shown that the boundary of a digital figure is a closed polygonal curve that belongs to a family of ordered crossing polygons. This family of polygons is best described as polygons such that no interior points lie to the left as the boundary is traversed in the clockwise direction, with no restriction on the possible occurrence of overlapping sides and collinear vertices. All simple polygons are shown to belong to this family. A formal proof of correctness is also included and a convex hull invariant condition is introduced. It is also shown that the convex hull invariant condition presented by S. K. Ghosh and R. K. Shyamasundar is a special case of the one presented here, and that theirs is necessary but not sufficient to guarantee the correctness of their algorithm for obtaining the convex hull of a simple polygon. The latter is proved by means of a counter-example. A comparative evaluation of the convex hull algorithm presented here with reference to other algorithms that have appeared in the recent literature is included. Pattern Recognition applications, in which both the convex hull and the convex deficiency of digital figures are used as shape descriptors, are briefly discussed.