6533b859fe1ef96bd12b77f3
RESEARCH PRODUCT
On the exhaustive generation of k-convex polyominoes
Paolo MassazzaStefano BrocchiGiusi Castiglionesubject
General Computer SciencePolyomino0102 computer and information sciences02 engineering and technologyComputer Science::Computational Geometry01 natural sciencesConvexityTheoretical Computer ScienceCombinatoricsCAT algorithmIntegerExhaustive generation0202 electrical engineering electronic engineering information engineeringConvex polyominoeConvexity K-convex polyominoes.Convex polyominoesComputer Science::DatabasesMathematicsDiscrete mathematicsAmortized analysisMathematics::CombinatoricsDegree (graph theory)Settore INF/01 - InformaticaComputer Science (all)Regular polygonMonotone polygon010201 computation theory & mathematicsPath (graph theory)020201 artificial intelligence & image processingCAT algorithms; Convex polyominoes; Exhaustive generation;CAT algorithmsdescription
The degree of convexity of a convex polyomino P is 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. In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino and we show how it can be used to design an algorithm that generates, given an integer k, all k-convex polyominoes of area n in constant amortized time, using space O(n). Furthermore, by applying few changes, we are able to generate all convex polyominoes whose degree of convexity is exactly k.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-01-01 |