Search results for "Polyomino"
showing 9 items of 19 documents
Enumeration of L-convex polyominoes by rows and columns
2005
In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once.Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the rational recurrence relation fn = 4fn-1 - 2fn-2, with f0 = 1, f1 = 2, f2 = 7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems.
Polyomino coloring and complex numbers
2008
AbstractUsually polyominoes are represented as subsets of the lattice Z2. In this paper we study a representation of polyominoes by Gaussian integers. Polyomino {(x1,y1),(x2,y2),…,(xs,ys)}⊂Z2 is represented by the set {(x1+iy1),(x2+iy2),…,(xs+iys)}⊂Z[i]. Then we consider functions of type f:P→G from the set P of all polyominoes to an abelian group G, given by f(x,y)≡(x+iy)m(modv), where v is prime in Z[i],1≤m<N(v) (N(v) is the norm of v). Using the arithmetic of the ring Z[i] we find necessary and sufficient conditions for such a function to be a coloring map.
On the exhaustive generation of k-convex polyominoes
2017
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.
A genetic algorithm for discrete tomography reconstruction
2007
The aim of this paper is the description of an experiment carried out to verify the robustness of two different approaches for the reconstruction of convex polyominoes in discrete tomography. This is a new field of research, because it differs from classic computerized tomography, and several problems are still open. In particular, the stability problem is tackled by using both a modified version of a known algorithm and a new genetic approach. The effect of both, instrumental and quantization noises has been considered too. © 2007 Springer Science+Business Media, LLC.
The Reconstruction of Polyominoes from Approximately Orthogonal Projections
2001
The reconstruction of discrete two-dimensional pictures from their projection is one of the central problems in the areas of medical diagnostics, computer-aided tomography, pattern recognition, image processing, and data compression. In this note, we determine the computational complexity of the problem of reconstruction of polyominoes from their approximately orthogonal projections. We will prove that it is NP-complete if we reconstruct polyominoes, horizontal convex polyominoes and vertical convex polyominoes. Moreover we will give the polynomial algorithm for the reconstruction of hv-convex polyominoes that has time complexity O(m3n3).
Disconnected Graph Layout and the Polyomino Packing Approach
2002
Conference name: GD: International Symposium on Graph Drawing 9th International Symposium Date of Conference: 23–26 September 2001 We review existing algorithms and present a new approach for layout of disconnected graphs. The new approach is based on polyomino representation of components as opposed to rectangles. The parameters of our algorithm and their influence on the drawings produced as well as a variation of the algorithm for multiple pages are discussed. We also analyze our algorithm both theoretically and experimentally and compare it with the existing ones. The new approach produces much more compact and uniform drawings than previous methods. © Springer-Verlag Berlin Heidelberg …
Ideals generated by the inner 2-minors of collections of cells
2023
In 2012 Ayesha Asloob Qureshi connected collections of cells to Commutative Algebra assigning to every collection $\mathcal{P}$ of cells the ideal of inner 2-minors, denoted by $I_{\mathcal{P}}$, in the polynomial ring $S_{\mathcal{P}}=K[x_v:v\text{ is a vertex of }\mathcal{P}]$. Investigating the main algebraic properties of $K[\mathcal{P}]=S_{\mathcal{P}}/I_{\mathcal{P}}$ depending on the shape of $\mathcal{P}$ is the purpose of this research. Many problems are still open and they seem to be fascinating and exciting challenges.\\ In this thesis we prove several results about the primality of $I_{\mathcal{P}}$ and the algebraic properties of $K[\mathcal{P}]$ like Cohen-Macaulyness, normali…
A Tomographical Characterization of L-convex Polyominoes
2005
Our main purpose is to characterize the class of L-convex polyominoes introduced in [3] by means of their horizontal and vertical projections. The achieved results allow an answer to one of the most relevant questions in tomography i.e. the uniqueness of discrete sets, with respect to their horizontal and vertical projections. In this paper, by giving a characterization of L-convex polyominoes, we investigate the connection between uniqueness property and unimodality of vectors of horizontal and vertical projections. In the last section we consider the continuum environment; we extend the definition of L-convex set, and we obtain some results analogous to those for the discrete case.
Highmann's Theorem on Discrete Sets
2006
In this paper we investigate properties of different classes of discrete sets with respect to the partial-order of subpicture. In particular we take in consideration the classes of convex polyominoes and L-convex polyominoes. In the first part of the paper we study closure properties of these classes with respect the order and we give a new characterization of L-convex polyominoes. In the second part we pose the question to extend Higman’s theoremto discrete sets. We give a negative answer in the general case and we prove that the set of L-convex polyominoes is well-partially-ordered by using a representation of L-convex polyominoes in terms of words of a regular language.