On computing the degree of convexity of polyominoes (Q490307): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: PCIF / rank | |||
Normal rank |
Revision as of 01:39, 28 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On computing the degree of convexity of polyominoes |
scientific article |
Statements
On computing the degree of convexity of polyominoes (English)
0 references
22 January 2015
0 references
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.
0 references
convex polyominoes
0 references
degree of convexity
0 references