×

A linear algorithm for construction of optimal digital convex \(2K\)-gons. (English) Zbl 0804.68149

Summary: The 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 a Farey sequence, while the construction for \(k\) odd uses, in addition, two families of auxiliary 6-gons.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
11B57 Farey sequences; the sequences \(1^k, 2^k, \dots\)
PDFBibTeX XMLCite