Detection of the discrete convexity of polyominoes
type: Item
instance of: scholarly article
title: Detection of the discrete convexity of polyominoes
zbMATH Open document ID: 1019.52008
DOI: 10.1016/S0166-218X(02)00227-5
author: Isabelle Debled-Rennesson
author: Jocelyne Rouyer-Degli
author: J. L. Rémy
published in: Discrete Applied Mathematics
publication date: 2003-03-09T00:00:00Z
review text: 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.
reviewed by: Mihai Cipu
Mathematics Subject Classification ID: 52A99
Mathematics Subject Classification ID: 05B50
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 1878515
zbMATH Keywords: discrete convexity
zbMATH Keywords: segmentation
zbMATH Keywords: discrete line
zbMATH Keywords: polyominoes
zbMATH Keywords: discrete tomography
zbMATH Keywords: linear algorithm
describes a project that uses: CHIP
MaRDI profile type: Publication
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Comparison of algorithms for reconstructing \(hv\)-convex discrete sets
cites work: Q2728902
cites work: Reconstructing convex polyominoes from horizontal and vertical projections
cites work: Introducing global constraints in CHIP
cites work: Q4471787
cites work: Reconstruction of 4- and 8-connected convex discrete sets from row and column projections
cites work: Q4277830
cites work: Reconstructing \(hv\)-convex polyominoes from orthogonal projections
cites work: Q4951148
cites work: Q4524013
cites work: The number of convex polyominoes reconstructible from their orthogonal projections
cites work: Q4524010
cites work: Generating convex polyominoes at random
cites work: Q3318142
cites work: Digital Convexity, Straightness, and Convex Polygons
cites work: Digital Straight Lines and Convexity of Digital Regions
cites work: Discrete tomography. Foundations, algorithms, and applications
cites work: Q4254883
cites work: Q5595902
cites work: Q4948843
cites work: The reconstruction of polyominoes from their orthogonal projections
full work available at URL: s0166-218x(02)00227-5
OpenAlex ID: W1827092650
description: scientific article; zbMATH DE number 1878515