On the Exhaustive Generation of k-ConvexPolyominoes

Risultato della ricerca: Other

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.
Lingua originaleEnglish
Numero di pagine8
Stato di pubblicazionePublished - 2014

Fingerprint Entra nei temi di ricerca di 'On the Exhaustive Generation of k-ConvexPolyominoes'. Insieme formano una fingerprint unica.

  • Cita questo