scientific article; zbMATH DE number 1444450

From MaRDI portal
Publication:4953527





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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4953527)