### Abstract

In this paper we present an algorithm which has as input a convex polyomino P and computes its degree of convexity, deﬁned 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 time complexity O(min(m, rk)), where r is the number of corners of P. Moreover, the algorithm leads naturally to a decomposition of P into simpler polyominoes.

Lingua originale | English |
---|---|

pagine (da-a) | 1-13 |

Numero di pagine | 13 |

Rivista | Electronic Journal of Combinatorics |

Volume | 22 |

Stato di pubblicazione | Published - 2015 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Entra nei temi di ricerca di 'On computing the degree of convexity of polyominoes'. Insieme formano una fingerprint unica.

## Cita questo

Castiglione, G., Brocchi, S., & Massazza, P. (2015). On computing the degree of convexity of polyominoes.

*Electronic Journal of Combinatorics*,*22*, 1-13.