Building on [Sati and Rossignac, 2016], we investigate the problem of defining and computing the average of digital curves. Given n digital curves that satisfy compatibility conditions, a set - called the gap - in which the average curve is looked for, is defined. The proposed definition rewrites the classical arithmetic mean for curves by (i) defining the distance between each point of the gap and its projection on each curve and (ii) computing the points that minimize the sum of squared deviations. We show that, algorithmically speaking, computing such projections comes down to computing a distance transform with visibility constraints. We propose a fast algorithm to compute a good approximation of these distance maps and finally show that the average curve can be obtained using classical watershed algorithm.