On the min DSS problem of closed discrete curves

Given a discrete eight-connected curve, it can be represented by discrete eight connected segments. In this paper, we try to determine the minimal number of necessary discrete segments. This problem is known as the min DSS problem. We propose to use a generic curve representation by discrete tangents, called a tangential cover which can be computed in linear time. We introduce a series of criteria each having a linear-time complexity to progressively solve the min DSS problem. This results in an optimal algorithm both from the point of view of optimization and of complexity, outperforming the previous quadratic bound.