On computing the degree of convexity of polyominoes

MaRDI QIDQ490307zbMATH OpenFDO

Authors Stefano Brocchi, G. Castiglione, P. Massazza

Publication date 22 January 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p7

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

convex polyominoesdegree of convexity

Mathematics Subject Classification ID

Polyominoes (05B50) Other problems of combinatorial convexity (52A37) Analysis of algorithms (68W40)

Review text

Summary: In this paper we present an algorithm which has as input a convex polyomino \(P\) and computes its degree of convexity, defined as the smallest integer \(k\) such that any two cells of \(P\) can be joined by a monotone path inside \(P\) with at most \(k\) changes of direction. The algorithm uses space \(O(m + n)\) to represent a polyomino \(P\) with \(n\) rows and \(m\) columns, and has a running time \(O(\min(m; r k))\), where \(r\) is the number of corners of \(P\). Moreover, the algorithm leads naturally to a decomposition of \(P\) into simpler polyominoes.

Recommendations

• On the exhaustive generation of \(k\)-convex polyominoes
• Detection of the discrete convexity of polyominoes
• scientific article; zbMATH DE number 992952
• On the generation of convex polyominoes
• Generating convex polyominoes at random

Cites work

• A method for the enumeration of various classes of column-convex polygons
• A reconstruction algorithm for L-convex polyominoes.
• A tiling system for the class of L-convex polyominoes
• Algebraic languages and polyominoes enumeration
• Checker Boards and Polyominoes
• Combinatorial aspects of \(L\)-convex polyominoes
• Counting k-convex polyominoes
• Detection of the discrete convexity of polyominoes
• Discrete Geometry for Computer Imagery
• On the generation and enumeration of some classes of convex polyominoes
• On the generation of convex polyominoes
• PCIF: an algorithm for lossless true color image compression
• Reconstruction of L-convex Polyominoes
• The number of Z-convex polyominoes

Cited in

(11)

• Detection of the discrete convexity of polyominoes
• Tomographic reconstruction of 2-convex polyominoes using dual Horn clauses
• scientific article; zbMATH DE number 992952 (Why is no real title available?)
• Computing deviations from convexity in polygons
• On counting Z-convex polyominoes
• Code for polyomino and computer search of isospectral polyominoes
• On the exhaustive generation of \(k\)-convex polyominoes
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Incremental algorithms based on discrete Green theorem.
• Asymptotics of Z-convex polyominoes
• Centered ascending polyominoes

Describes a project that uses

Uses Software

• PCIF

This page was built for publication: On computing the degree of convexity of polyominoes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490307)