Detection of the discrete convexity of polyominoes (Q1861555)

The paper deals with the notion of discrete convexity introduced by \textit{C. E. Kim} and \textit{A. Rosenfeld} [IEEE Trans. Pattern Anal. Mach. Intell. 4, 149-153 (1982; Zbl 0485.52007)]: a discrete region \(R\) is convex if its convex hull contains no discrete points of the complement of \(R\). A discrete region \(P\) is called polyomino if any couple of cells may be linked through a path containing only horizontal and vertical moves. A polyomino is \(hv\)-convex when cells of each row and each column are consecutive. Using only these definitions, the authors devise a simple algorithm to detect the convexity of a \(hv\)-polyomino. The main contribution of the paper under review is a linear algorithm for checking the convexity on the curve points of the border. Correctness of the method hinges on a new result on the construction of the convex hull of a discrete line segment. Preliminary conclusions on testing the discrete convexity of polyominoes by using the methods of constraint programming are reported.