An Arithmetical Characterization of the Convex Hull of Digital Straight Segments

International audienceIn this paper, we arithmetically describe the convex hull ofa digital straight segment by three recurrence relations. This charac-terization gives new insights into the combinatorial structure of digitalstraight segments of arbitrary length and intercept. It also leads to twoon-line algorithms that computes a part of the convex hull of a givendigital straight segment. They both run in constant space and constanttime per vertex. Due to symmetries, they are enough to reconstructthe whole convex hull. Moreover, these two algorithms provide efficientsolutions to the subsegment problem, which consists in computing theminimal parameters of a segment of a digital straight line of known pa-rameters. Due to its close link to the subsegment problem, this workhelps to understand the effects of length and intercept on segments ofparallel digital straight lines, such as sections of a piece of digital planeor sub-sampled digital straight segments