Skip to main content
Passa alla visualizzazione normale.

GIUSEPPA CASTIGLIONE

On the Exhaustive Generation of k-Convex Polyominoes

  • Authors: Brocchi, S.; Castiglione, G.; Massazza, P.
  • Publication year: 2014
  • Type: Proceedings (TIPOLOGIA NON ATTIVA)
  • Key words: Convexity, K-convex polyominoes.
  • OA Link: http://hdl.handle.net/10447/99388

Abstract

In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino, 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. We show how it can be used to obtain an efficient algorithm for computing all k-convex polyominoes of size n. More precisely, such an algorithm uses space O(n) and runs in constant amortized time.