An Algorithm for a Simple Construction of Suboptimal Digital Convex Polygons


Dragan M. Acketa, Snežana Matić-Kekić




The relationship between the number of edges and the diameter of digital convex polygons was studied in the papers [6], [2], [3], [4], This paper give a linear algorithm (w.r.t. the number vertices) for a simple approximate construction of optimal digital convex polygons, that is, those digital convex polygons, which have the smallest possible diameter for a given number of edges. The algorithm partly uses the efficient construction [2] of a special sequence of optimal digital convex polygons. It constructs in a simplified manner the suboptimal (with error tolerance equal to 1) digital convex polygons. The proofs of this suboptimality can be found in the paper [4].