This paper gives a linear algorithm (w.r.t . the number of vertices) for a construction of optimal digital convex 2k-gons, that is, those digital convex polygons, which have the smallest possible diameter with a given even number of edges. The construction for k even is based on the efficient construction of Farey sequence, while the construction for k odd uses, in addition, two families of auxiliary 6-gons.