On computing the degree of convexity of polyominoes

Giuseppa Castiglione, Stefano Brocchi, Paolo Massazza

Risultato della ricerca: Articlepeer review

3 Citazioni (Scopus)


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 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 originaleEnglish
pagine (da-a)1-13
Numero di pagine13
RivistaElectronic Journal of Combinatorics
Stato di pubblicazionePublished - 2015

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.2600.2608???
  • ???subjectarea.asjc.2600.2607???
  • ???subjectarea.asjc.1700.1703???
  • ???subjectarea.asjc.2600.2604???


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

Cita questo