No label defined (Q4953527)

A digital convex polygon is a polygon with all the vertices belonging to the integer grid and with all the angles strictly less than \(\pi \) radians. The following optimization problem is considered: Given a digital convex \(n\)-gon, add congruent parallel edges to it in such a way that a digital convex \((n+2)\)-gon is produced and that the area difference between these two polygons is minimal possible. An \(O(n\cdot s)\) algorithm is presented for a given digital convex \(2n\)-gon \(P\), where \(s\) denotes the minimal edge size of a digital square in which \(P\) can be described. It is shown that this algorithm can be generalized for more general case preserving the same complexity.