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]

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]

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]

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 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]

We consider variations of the original art gallery problem where the domain is a polyomino, a polycube, or a polyhypercube. An m -polyomino is the connected union of m unit squares called pixels, an m -polycube is the connected union of m unit cubes called voxels, and an m -polyhypercube is the connected union of m unit hypercubes in a d dimensional Euclidean space. In this paper we generalize and unify the known results about guarding polyominoes and polycubes and obtain simpler proofs. We also obtain new art gallery theorems for guarding polyhypercubes. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we introduce a family of infinite words that generalize the Fibonacci word and we study their combinatorial properties. We associate with this family of words a family of curves that are like the Fibonacci word fractal and reveal some fractal features. Finally, we describe an infinite family of polyominoes stems from the generalized Fibonacci words and we study some of their geometric properties, such as perimeter and area. These last polyominoes generalize the Fibonacci snowflake and they are double squares polyominoes, i.e., tile the plane by translation in exactly two distinct ways. [Copyright &y& Elsevier]

Abstract: We prove a generalization of a conjecture of Dokos, Dwyer, Johnson, Sagan, and Selsor giving a recursion for the inversion polynomial of 321-avoiding permutations. We also answer a question they posed about finding a recursive formula for the major index polynomial of 321-avoiding permutations. Other properties of these polynomials are investigated as well. Our tools include Dyck and 2-Motzkin paths, polyominoes, and continued fractions. [Copyright &y& Elsevier]

Abstract: We study the combinatorial properties and the problem of generating exhaustively double square tiles, i.e. polyominoes yielding two distinct periodic tilings by translated copies such that every polyomino in the tiling is surrounded by exactly four copies. We show in particular that every prime double square tile may be obtained from the unit square by applying successively some invertible operators on double squares. As a consequence, we prove a conjecture of Provençal and Vuillon (2008) [17] stating that these polyominoes are invariant under rotation by angle . [Copyright &y& Elsevier]

Abstract: In this paper, we consider the generation of three classes of polyominoes, distinguished by their connectivity type. We present a two-player game called gomino, and we show how this game induces an algorithm to generate these sets of polyominoes according to their site-perimeter. We then use a variation of the gomino algorithm to obtain exact expressions for the number of polyominoes inscribed in a rectangle of size with area , where . [Copyright &y& Elsevier]

Abstract: In this paper we deal with uniqueness and reconstruction problems in Discrete Tomography. For a finite set of directions in , we introduce the class of -inscribable lattice sets, and give a detailed description of their geometric structure. This shows that such sets can be considered as the natural discrete counterpart of the same notion known in the continuous case, as well as a kind of generalization of the class of the so-called -convex polyominoes (or moon polyominoes). In view of reconstruction from projections along the directions in , two related questions of tomographic interest are investigated, namely uniqueness and additivity. We show that both properties are fulfilled by -inscribable lattice sets. Moreover, concerning the case , we provide an explicit reconstruction algorithm from the knowledge of directed horizontal and vertical X-rays, jointly with a few preliminary results towards a possible sharp stability inequality. [Copyright &y& Elsevier]

Abstract: We investigate tiling problems for regions in a square lattice by ribbon -shaped tetrominoes. Our results show that tiling of the first quadrant by ribbon -tetrominoes is possible only if it reduces to a tiling by 2×4 and 4×2 rectangles. A consequence is the description of all rectangles that can be tiled by ribbon -shaped tetrominoes. [Copyright &y& Elsevier]

Abstract: We prove that the number of monomer-dimer tilings of an square grid, with monomers in which no four tiles meet at any point is , when m and n have the same parity. In addition, we present a new proof of the result that there are such tilings with n monomers, which divides the tilings into n classes of size . The sum of these tilings over all monomer counts has the closed form and, curiously, this is equal to the sum of the squares of all parts in all compositions of n. We also describe two algorithms and a Gray code ordering for generating the tilings with n monomers, which are both based on our new proof. [Copyright &y& Elsevier]

Abstract: It has been proved that, among the polyominoes that tile the plane by translation, the so-called squares tile the plane in at most two distinct ways. In this paper, we focus on double squares, that is, the polyominoes that tile the plane in exactly two distinct ways. Our approach is based on solving equations on words, which allows us to exhibit properties about their shape. Moreover, we describe two infinite families of double squares. The first one is directly linked to Christoffel words and may be interpreted as segments of thick straight lines. The second one stems from the Fibonacci sequence and reveals some fractal features. [Copyright &y& Elsevier]

Abstract: We introduce the problem of polyomino Gray codes, which is the listing of all members of certain classes of polyominoes such that successive polyominoes differ by some well-defined closeness condition (e.g., the movement of one cell). We discuss various closeness conditions and provide several Gray codes for the class of column-convex polyominoes with a fixed number of cells in each column. For one of our closeness conditions, a natural new class of distributive lattice arises: the partial order is defined on the set of -tuples , where each and , and the cover relations are and . We also discuss some properties of this lattice. [Copyright &y& Elsevier]

Abstract: Poly-antimatroids are generalization of the notion of antimatroid to multisets. When the underlying set consists of only two elements, such two-dimensional poly-antimatroids correspond to point sets in the integer lattice . In this research we concentrate on geometrical properties of two-dimensional poly-antimatroids and prove that these sets form distributive lattice polyhedra. Our findings imply that two-dimensional poly-antimatroids have convex dimension 2. Further we investigate geometrical properties of three-dimensional distributive lattice polyhedra. [Copyright &y& Elsevier]

Abstract: In a polyomino set (1, 2)-achievement game the maker and the breaker alternately mark one and two previously unmarked cells respectively. The maker’s goal is to mark a set of cells congruent to one of a given set of polyominoes. The breaker tries to prevent the maker from achieving his goal. The teams of polyominoes for which the maker has a winning strategy is determined up to size 4. In set achievement games, it is natural to study infinitely large polyominoes. This enables the construction of super winners that characterize all winning teams up to a certain size. [Copyright &y& Elsevier]

Abstract: Let the space be divided into unit squares where a polyomino is a finite, connected set of unit squares. In this paper, we give a necessary and sufficient condition on tessellating polyominos by observing an unexpected relation between such tessellations and systems of arithmetic progressions. [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new class of binary matrices whose entries show periodical configurations, and we furnish a first approach to their analysis from a tomographical point of view. In particular we propose a polynomial-time algorithm for reconstructing matrices with a special periodical behavior from their horizontal and vertical projections. We succeeded in our aim by using a reduction involving polyominoes which can be characterized by means of formulas. [Copyright &y& Elsevier]

Abstract: The problem of reconstructing a convex polyominoes from its horizontal and vertical projections when the projections are defined as the number of cells of the polyomino in the different lines and columns was studied by Del Lungo and M. Nivat. In this paper, we study the reconstruction of any convex polyomino when the orthogonal projections are defined as the contour length of the object intercepted by the ray. We prove the NP-hardness of this problem for several classes of polyominoes: general, h-convex, -convex. For -convex polyominoes we give a polynomial time algorithm for the reconstruction problem. [Copyright &y& Elsevier]

Abstract: Using computer programs, we enumerate and classify the tiling behavior of small polyominoes (), polyhexes (), and polyiamonds (). For tiles that tile the Euclidean plane, we give diagrams illustrating how they tile. We also show several larger tiles whose minimal fundamental domain in any admitted (periodic) tiling is significantly larger than for any previously known tile. [Copyright &y& Elsevier]

Abstract: Polyomino achievement games on 3-dimensional rectangular boards are studied. All except two polyominoes with less than six cells are weak winners. The smallest known paving losers contain six cells. There are finitely many winning polyominoes. [Copyright &y& Elsevier]

In this paper we give a new undecidability result about tiling problems. Given a finite set of polyomino types, the problem whether this set is a code, is undecidable. The same result holds for dominoes. [Copyright &y& Elsevier]

A polyomino is a finite, edge-connected set of cells in the plane. At the present time, an enumeration of all polyominoes is nowhere in sight. On the other hand, there are several subsets of polyominoes for which generating functions are known. For example, there exists extensive knowledge about column-convex polyominoes, a model introduced by Temperley in 1956. While studying column-convex polyominoes, researchers also gave a look at diagonally convex polyominoes (DCPs), but noticed an awkward feature: when the last diagonal of a DCP is deleted, the remaining object is not always a polyomino. So researchers focused their attention on directed DCPs. (A directed DCP is such a DCP that remains a polyomino when, for any i , its last i diagonals are deleted.) Directed DCPs gradually became well understood, whereas general DCPs have remained unexplored up to now. In this paper, we finally face general DCPs. Modulo a little trick, which saves us from dealing with non-polyominoes, we use the layered approach (described in chapter 3 of the book "Polygons, Polyominoes and Polycubes", edited by Anthony Guttmann). The computations are of remarkable bulk. Our main result is the perimeter generating function for DCPs; we denote it D (d , x). The function D (d , x) is algebraic and satisfies an equation of degree eight. The formula for D (d , x) is about three pages long. That formula involves nine polynomials in d and x , and each of those polynomials is of degree 58 or more in x. [ABSTRACT FROM AUTHOR]

The core problem of discrete tomography, i.e., the faithful reconstruction of an unknown discrete object from projections along a given set of directions, is ill-posed in general. When further constraints are imposed on the object or on the employed directions, uniqueness of the reconstruction can be obtained. It is the case, for example, of convex lattice sets in Z 2 , for which a theorem by Gardner and Gritzmann assures the faithful reconstruction when suitable sets of directions are considered. It was conjectured that a similar result holds for the class of hv-convex polyominoes. In this paper we are concerned with this conjecture, providing new 4-tuples of discrete directions that do not lead to a unique reconstruction of hv-convex polyominoes, underlining the relevant structural difference with the class of convex sets. Our result is based on the recursive definition of new hv-convex switching components on discrete sets along four directions. [ABSTRACT FROM AUTHOR]