Search

In this paper we consider rectangular billiard tables having vertices with integer coordinates, and side lengths equal to integer multiples of the norms of the side directions. We also assume that all the bouncing points of a billiard ball are constrained to belong to the integer lattice Z 2. We address several questions concerning combinatorial and geometric properties of the allowed orbits, that, due to the integer constraint, are called integer orbits. We give a complete classification of integer orbits, and the parameters contributing to their structure are precisely determined. This leads to understand how the orbit fills the lattice billiard before it really propagates. In particular, one can characterize the trajectories that reach a billiard pocket, as well as all the closed orbits, by the simple knowledge of the size of the billiard table, and of the starting moving direction. The characterization bases on the explicit determination of the numerical sequences corresponding to clockwise, and counterclockwise, bouncing. We also investigate the geometrical structure of an allowed orbit in terms of special sub-patterns, called Z -paths, pointing out the allowed lengths of different Z -paths in a same orbit. This is of independent interest, and is related to the configurations known as switching components, that play a crucial role in discrete tomography, and in problems concerning image reconstruction. [ABSTRACT FROM AUTHOR]

Finite distributive lattices whose join-meet ideals are of König type will be classified. Furthermore, a class of polyominoes whose polyomino ideals are of König type will be studied. [ABSTRACT FROM AUTHOR]

A monotonous polyomino is formed by all lattice unit squares met by the graph of some fixed monotonous continuous function f : [ a , b ] → R with f (k) ∉ Z whenever k ∈ Z . Our main result says that the least cardinality of a covering of a lattice (m × n) -rectangle by monotonous polyominoes is ⌈ 2 3 (m + n - m 2 + n 2 - m n) ⌉. The paper is motivated by a problem on arrangements of straight lines on chessboards. [ABSTRACT FROM AUTHOR]

In this work we study the most restrictive variety of graceful labeling, that is, we study the existence of an α-labeling for some families of graphs that can be embedded in the integral grid. Among the categories of graphs considered here we have a subfamily of 2-link fences, a subfamily of column-convex polyominoes, and a subfamily of irregular cyclic-snakes. We prove that under some conditions, the α-labeling of these graphs can be transformed into a harmonious labeling. We also present a closed formula for the number of 2-link fences examined here. [ABSTRACT FROM AUTHOR]

We show that translational tiling of the plane with a set of 8 polyominoes is undecidable, which answers a question posted by Ollinger. The techniques employed in our proof include a different orientation for simulating the Wang tiles in polyomino and a new method for encoding the colors of Wang tiles. [ABSTRACT FROM AUTHOR]

Reconstructing a discrete object by means of X-rays along a finite set U of (discrete) directions represents one of the main task in discrete tomography. Indeed, it is an ill-posed inverse problem, since different structures exist having the same projections along all lines whose directions range in U. Characteristic of ambiguous reconstructions are special configurations, called switching components, whose understanding represents a main issue in discrete tomography, and an independent interesting geometric problem as well. The investigation of switching component usually bases on some kind of prior knowledge that is incorporated in the tomographic problem. In this paper, we focus on switching components under the constraint of convexity along the horizontal and the vertical directions imposed to the unknown object. Moving from their geometric characterization in windows and curls, we provide a numerical description, by encoding them as special sequences of integers. A detailed study of these sequences leads to the complete understanding of their combinatorial structure, and to a polynomial-time algorithm that explicitly reconstructs any of them from a pair of integers arbitrarily given. [ABSTRACT FROM AUTHOR]

A bijection is given between the set of directed column-convex polyominoes on triangular and honeycomb lattices of area n and some families of restricted compositions. This is an analogous result to one given by Deutsch and Prodinger for polyominoes over square lattices. As a byproduct, we deduce new close forms for the number of hexagonal and triangular directed column-convex polyominoes of area n with k columns. [ABSTRACT FROM AUTHOR]

The homology group of a tiling introduced by M. Reid is studied for certain topological tilings. As in the planar case, for finite square grids on topological surfaces, the method of homology groups, namely the non-triviality of some specific element in the group allows a 'coloring proof' of impossibility of a tiling. Several results about the non-existence of polyomino tilings on certain square-tiled surfaces are proved in the paper. [ABSTRACT FROM AUTHOR]

We investigate (0 , 1) -matrices that are convex , which means that the ones are consecutive in every row and column. These matrices occur in discrete tomography. The notion of ranked essential sets, known for permutation matrices, is extended to convex sets. We show a number of results for the class C (R , S) of convex matrices with given row and column sum vectors R and S. Also, it is shown that the ranked essential set uniquely determines a matrix in C (R , S). [ABSTRACT FROM AUTHOR]

We study the effects of non-determinism and gene duplication on the structure of genotype–phenotype (GP) maps by introducing a non-deterministic version of the Polyomino self-assembly model. This model has previously been used in a variety of contexts to model the assembly and evolution of protein quaternary structure. Firstly, we show the limit of the current deterministic paradigm which leads to built-in anti-correlation between evolvability and robustness at the genotypic level. We develop a set of metrics to measure structural properties of GP maps in a non-deterministic setting and use them to evaluate the effects of gene duplication and subsequent diversification. Our generalized versions of evolvability and robustness exhibit positive correlation for a subset of genotypes. This positive correlation is only possible because non-deterministic phenotypes can contribute to both robustness and evolvability. Secondly, we show that duplication increases robustness and reduces evolvability initially, but that the subsequent diversification that duplication enables has a stronger, inverse effect, greatly increasing evolvability and reducing robustness relative to their original values.

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The cardinality of a forcing set of M with the smallest size is called the forcing number of M, denoted by f(G, M). The forcing spectrum of G is defined as: Spec(G) = {f(G, M)∣ M is a perfect matching of G}. In this paper, by applying the Z-transformation graph (resonance graph) we show that for any polyomino with perfect matchings and any even polygonal chain, their forcing spectra are integral intervals. Further we obtain some sharp bounds on maximum and minimum forcing numbers of hexagonal chains with given number of kinks. Forcing spectra of two extremal chains are determined. [ABSTRACT FROM AUTHOR]

How many chess rooks or queens does it take to guard all squares of a given polyomino, the union of square tiles from a square grid? This question is a version of the art gallery problem in which the guards can "see" whichever squares the rook or queen attacks. We show that ⌊ n 2 ⌋ rooks or ⌊ n 3 ⌋ queens are sufficient and sometimes necessary to guard a polyomino with n tiles. We then prove that finding the minimum number of rooks or queens needed to guard a polyomino is NP-hard. These results also apply to d-dimensional rooks and queens on d-dimensional polycubes. Finally, we use bipartite matching theorems to describe sets of non-attacking rooks on polyominoes. [ABSTRACT FROM AUTHOR]

Intellectual property (IP) reuse is a well-known technique in chip design industry. But this technique also exposes a security vulnerability called IP stealing attack. Network-on-Chip (NoC) is an on-chip scalable communication medium and is used as an IP and sold by various vendors to be integrated in a Multiprocessor System-on-Chip (MPSoC). An attacker can launch IP stealing attack against NoC IP. In this article,we propose a NoC IP protection technique called circular path--based fingerprinting (CPF) using fingerprint embedding. We also provide a theoretical model using polyomino theory to get the number of distinct fingerprints in a NoC. We show that our proposed technique requires much less hardware overhead compared to an existing NoC IP security solution and also provides better security against removal and masking attacks. In particular, our proposed CPF technique requires 27.41% less router area compared to the existing solution. We also show that our CPF solution does not affect the normal packet latency and hence does not degrade the NoC performance. [ABSTRACT FROM AUTHOR]

A planar Tangle is a smooth simple closed curve piecewise defined by quadrants of circles with constant curvature. We can enumerate Tangles by counting their dual graphs, which consist of a certain family of polysticks. The number of Tangles with a given length or area grows exponentially, and we show the existence of their growth constants by comparing Tangles to two families of polyominoes. [ABSTRACT FROM AUTHOR]

Contact graphs have emerged as an important tool in the study of translative packings of convex bodies. The contact number of a packing of translates of a convex body is the number of edges in the contact graph of the packing, while the Hadwiger number of a convex body is the maximum vertex degree over all such contact graphs. In this paper, we investigate the Hadwiger and contact numbers of totally separable packings of two-dimensional convex bodies, which we refer to as the separable Hadwiger number and the separable contact number, respectively. We show that the separable Hadwiger number of any two-dimensional smooth convex body is 4 and the maximum separable contact number of any packing of n translates of a two-dimensional smooth strictly convex body is 2 n - 2 n . Our proofs employ a characterization of total separability in terms of hemispherical caps on the boundary of a convex body, Auerbach bases of finite dimensional real normed spaces, angle measures in real normed planes, minimal perimeter polyominoes and an approximation of two-dimensional o -symmetric smooth strictly convex bodies by, what we call, Auerbach domains. [ABSTRACT FROM AUTHOR]

A plane tiling by the copies of a polyomino is called isohedral if every pair of copies in the tiling has a symmetry of the tiling that maps one copy to the other. We show that, for every n -omino (i.e., polyomino consisting of n cells), the number of non-equivalent isohedral tilings generated by 90 degree rotations, so called p4-tilings or quarter-turn tilings, is bounded by a constant (independent of n). The proof relies on the analysis of the factorization of the boundary word of a polyomino. We also show an example of a polyomino that has three non-equivalent p4-tilings. [ABSTRACT FROM AUTHOR]

We study a problem about the number of lattice plane tilings by the given area centrosymmetrical polyominoes. A polyomino is a connected plane geomatric figure formed by joiining a finite number of unit squares edge to edge. At present, various combinatorial enumeration problems connected to the polyomino are actively studied. There are some interesting problems on enuneration of various classes of polyominoes and enumeration of tilings of finite regions or a plane by polyominoes. In particular, the tiling is a lattice tiling if each tile can be mapped to any other tile by a translation which maps the whole tiling to itself. Earlier we proved that, for the number T(n) of a lattice plane tilings by polyominoes of an area n, holds the inequalities 2n−3 + 2[ n−3 2 ] ≤ T(n) ≤ C(n + 1)3 (2, 7)n+1 . In the present work we prove a similar estimate for the number of lattice tilings with an additional central symmetry. Let Tc(n) be a number of lattice plane tilings by a given area centrosymmetrical polyominoes such that its translation lattice is a sublattice of Z 2 . It is proved that C1( √ 2)n ≤ Tc(n) ≤ C2n 2 ( √ 2.68)n . In the proof of a lower bound we give an explicit construction of required lattice plane tilings. The proof of an upper bound is based on a criterion of the existence of lattice plane tiling by polyominoes, and on the theory of self-avoiding walks on a square lattice.

If a graph G is Pfaffian, then the number of perfect matchings of G can be computed in polynomial time. So it makes sense to test whether a graph is Pfaffian. Historically in organic chemistry and combinatorial mathematics, polyominos have attracted the most attention. In this paper, we characterize all Pfaffian polyominos on the Klein bottle. [ABSTRACT FROM AUTHOR]

Abstract We present recursive formulas giving the maximal number of leaves in tree-like polyforms living in two-dimensional regular lattices and in tree-like polycubes in the three-dimensional cubic lattice. We call these tree-like polyforms and polycubes fully leafed. The proof relies on a combinatorial algorithm that enumerates rooted directed trees that we call abundant. In the last part, we concentrate on the particular case of polyforms and polycubes, that we call saturated , which is the family of fully leafed structures that maximize the ratio (number of leaves) / (number of cells). In the polyomino case, we present a bijection between the set of saturated tree-like polyominoes of size 4 k + 1 and the set of tree-like polyominoes of size k. We exhibit a similar bijection between the set of saturated tree-like polycubes of size 41 k + 28 and a family of polycubes, called 4-trees, of size 3 k + 2. [ABSTRACT FROM AUTHOR]

We have entered an era of prosumer culture, where consumers have become producers. This democratisation impacts on all scales of production, including that of architecture. The Polyomino research agenda at the University of Southern California, Los Angeles has been developed by architect, programmer and gaming designer Jose Sanchez to explore ethical forms of participation through growth of the commons, and to reconsider the role of parts in production. Here he explains the issues at stake, as illustrated by some of Polyomino's outcomes. [ABSTRACT FROM AUTHOR]

We describe a class of fixed polyominoes called k -omino towers that are created by stacking rectangular blocks of size k × 1 on a convex base composed of these same k -omino blocks. By applying a partition to the set of k -omino towers of fixed area k n , we give a recurrence on the k -omino towers therefore showing the set of k -omino towers is enumerated by a Gauss hypergeometric function. The proof in this case implies a more general hypergeometric identity with parameters similar to those given in a classical result of Kummer. [ABSTRACT FROM AUTHOR]

The behaviour of a bad Tetris player suggests a class of polyominoes that we call prefix-closed. Such a class contains all polyominoes P such that for any integer i > 0 the first i columns of P form a polyomino. We provide a simple discrete dynamical system that allows us to define an algorithm for generating all prefix-closed polyominoes of size n in constant amortized time using O ( n ) space. [ABSTRACT FROM AUTHOR]

We give exact formulas for the bivariate generating series of 321-avoiding affine permutations with respect to rank and Coxeter length. We use two different combinatorial approaches, both based on the theory of heaps of pieces. [ABSTRACT FROM AUTHOR]

A new code, binary 2-dimentional code (B2DC), is proposed for polyominoes. An algorithm based on the B2DC and the reverse search method are proposed for enumerating nonisomorphic planar simply connected polyominoes. An enumeration tree and a new father-son relationship are defined for enumerating polyominoes. Then we propose an algorithm to build adjacent matrices and laplacian matrices by B2DCs of polyominoes and search isospectral polyomino graphs by computing characteristic polynomials of those matrices. [ABSTRACT FROM AUTHOR]

We study a problem of a number of lattice plane tilings by given area polyominoes. A polyomino is a connected plane geometric figure formed by joining edge to edge a finite number of unit squares. A tiling is a lattice tiling if each tile can be mapped to any other tile by translation which maps the whole tiling to itself. Let T(n) be a number of lattice plane tilings by given area polyominoes such that its translation lattice is a sublattice of Z². It is proved that 2n−3 + 2[ n−3 2 ] ≤ T(n) ≤ C(n + 1)3 (2.7)n+1. In the proof of a lower bound we give an explicit construction of required lattice plane tilings. The proof of an upper bound is based on a criterion of the existence of lattice plane tiling by polyomino and on the theory of self-avoiding walk. Also, it is proved that almost all polyominoes that give lattice plane tilings have sufficiently large perimeters.