Two linear-time algorithms for computing the minimum length polygon of a digital contour (Q765322)

The minimum length polygon (MLP) is used for approaching the geometry of a digital object. One of the possible definitions is to call it the polygon of minimum perimeter which stays in the band of one-pixel wide centered on the digital contour. Several algorithms for computing the MLP have been published but their time complexity is not linear or the used data structure is very complex. The authors of the article under review show that MLP has strong arithmetic and combinatorial properties. They present two new definitions related to the digital contour and new optimal time integer-only algorithms for computing it. One of these new definitions says that the arithmetic MLP of a digital contour is a polygon defined by so-called zones. The combinatorial MLP of a digital contour is defined using a simple algorithm based on computation vertices, which can be found in this paper. This paper contains the full theoretical background for understanding the main problems of the minimal length polygon of digital contours. Some illustrations of the results complete the paper.