On Computing the Degree of Convexity of Polyominoes

  • Stefano Brocchi
  • Giuseppa Castiglione
  • Paolo Massazza
Keywords: Convex polyominoes, Degree of convexity

Abstract

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.

Published
2015-01-09
Article Number
P1.7