Geodesic
On computing the degree of convexity of polyominoes
Stefano Brocchi1 ; Giuseppa Castiglione2 ; Paolo Massazza3
1University of Firenze
2University of Palermo
3University of Insubria
The electronic journal of combinatorics, Tome 22 (2015) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/3678
Classification : 05B50, 52A37, 68W40
Mots-clés : convex polyominoes, degree of convexity

Stefano Brocchi  1   ; Giuseppa Castiglione  2   ; Paolo Massazza  3

1 University of Firenze
2 University of Palermo
3 University of Insubria 
@article{10_37236_3678,
     author = {Stefano Brocchi and Giuseppa Castiglione and Paolo Massazza},
     title = {On computing the degree of convexity of polyominoes},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {1},
     doi = {10.37236/3678},
     zbl = {1305.05045},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3678/}
}
TY  - JOUR
AU  - Stefano Brocchi
AU  - Giuseppa Castiglione
AU  - Paolo Massazza
TI  - On computing the degree of convexity of polyominoes
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3678/
DO  - 10.37236/3678
ID  - 10_37236_3678
ER  - 
%0 Journal Article
%A Stefano Brocchi
%A Giuseppa Castiglione
%A Paolo Massazza
%T On computing the degree of convexity of polyominoes
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3678/
%R 10.37236/3678
%F 10_37236_3678
Stefano Brocchi; Giuseppa Castiglione; Paolo Massazza. On computing the degree of convexity of polyominoes. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/3678

Cité par Sources :