Helly Numbers of Polyominoes

We define the Helly number of a polyomino P as the smallest number h such that the h-Helly property holds for the family of symmetric and translated copies of P on the integer grid. We prove the following: (i) the only polyominoes with Helly number 2 are the rectangles, (ii) there does not exist any polyomino with Helly number 3, (iii) there exist polyominoes of Helly number k for any k ≠ 1, 3.     

Isohedral Polyomino Tiling of the Plane

A polynomial time algorithm is given for deciding, for a given polyomino P , whether there exists an isohedral tiling of the Euclidean plane by isometric copies of P . The decidability question for general tilings by copies of a single polyomino, or even periodic tilings by copies of a single polyomino, remains open. Received June 23, 1997, and in revised form April 6, 1998.     

Many L-Shaped Polyominoes Have Odd Rectangular Packings

A polyomino is called odd if it can tile a rectangle using an odd number of copies. We give a very general family of odd polyominoes. Specifically, consider an L-shaped polyomino, i.e., a rectangle that has a rectangular piece removed from one corner. For some of these polyominoes, two copies tile a rectangle, called a basic rectangle. We prove that such a polyomino is odd if its basic rectangle has relatively prime side lengths. This general family encompasses several previously known families of odd polyominoes, as well as many individual examples. We prove a stronger result for a narrower family of polyominoes. Let L _n denote the polyomino formed by removing a 1 ×  (n?2) corner from a 2 ×  (n?1) rectangle. We show that when n is odd, L _n tiles all rectangles both of whose sides are at least 8n ³, and whose area is a multiple of n. If we only allow L _n to be rotated, but not reflected, then the same is true, provided that both sides of the rectangle are at least 16n ⁴. We also give several isolated examples of odd polyominoes.     

Irregular polyomino tiling via integer programming with application in phased array antenna design

A polyomino is a generalization of the domino and is created by connecting a fixed number of unit squares along edges. Tiling a region with a given set of polyominoes is a hard combinatorial optimization problem. This paper is motivated by a recent application of irregular polyomino tilings in the design of phased array antennas. Specifically, we formulate the irregular polyomino tiling problem as a nonlinear exact set covering model, where irregularity is incorporated into the objective function using the information-theoretic entropy concept. An exact solution method based on a branch-and-price framework along with novel branching and lower-bounding schemes is proposed. The developed method is shown to be effective for small- and medium-size instances of the problem. For large-size instances, efficient heuristics and approximation algorithms are provided. Encouraging computational results including phased array antenna simulations are reported.     

On translating one polyomino to tile the plane

Given a polyomino, we prove that we can decide whether translated copies of the polyomino can tile the plane. Copies that are rotated, for example, are not allowed in the tilings we consider. If such a tiling exists the polyomino is called anexact polyomino. Further, every such tiling of the plane by translated copies of the polyomino is half-periodic. Moreover, all the possible surroundings of an exact polyomino are described in a simple way.     

On the Tiling System Recognizability of Various Classes of Convex Polyominoes

We consider some problems concerning two relevant classes of two-dimensional languages, i.e., the tiling recognizable languages, and the local languages, recently introduced by Giammarresi and Restivo and already extensively studied. We show that various classes of convex and column-convex polyominoes can be naturally represented as two-dimensional words of tiling recognizable languages. Moreover, we investigate the nature of the generating function of a tiling recognizable language, providing evidence that such a generating function need not be D-finite.     

Packing polyominoes clumsily

For a set D of polyominoes, a packing of the plane with D is a maximal set of copies of polyominoes from D that are not overlapping. A packing with smallest density is called a clumsy packing. We give an example of a set D such that any clumsy packing is aperiodic. In addition, we compute the smallest possible density of a clumsy packing when D consists of a single polyomino of a given size and show that one can always construct a periodic packing arbitrarily close in density to the clumsy packing.     

Avoiding Monotone Chains in Fillings of Layer Polyominoes

In this paper we give simple bijective proofs that the number of fillings of layer polyominoes with no northeast chains is the same as the number with no southeast chains. We consider 01-fillings and \({{\mathbb{N}}}\)-fillings and prove the results for both strong chains where the smallest rectangle containing the chain is also in the polyomino, and for regular chains where only the corners of the smallest rectangle containing the chain are required to be in the polyomino.     

Gröbner bases of balanced polyominoes

We introduce balanced polyominoes and show that their ideal of inner minors is a prime ideal and has a squarefree Gröbner basis with respect to any monomial order, and we show that any row or column convex and any tree‐like polyomino is simple and balanced.     

Rectangular Tiling in Multidimensional Arrays

We study the following tiling problem in d dimensions: given a d-dimensional rectangular array of nonnegative numbers and an integer p, partition the array into at most p rectangular subarrays so that the maximum weight of any subarray is minimized; the weight of a subarray is the sum of its elements. The rectangular tiling problem is motivated by applications in data mining, data partitioning, and video compression. Recently, Khanna, Muthukrishnan, and Paterson [SODA '98], showed that the tiling problem is NP-complete and gave a 2.5-approximation algorithm for d = 2.In this paper, we extend their result to multidimensional arrays and give an algorithm with approximation ratio , for d ≥ 2. The algorithm can be implemented to run in worst-case time O(N + p log N) time, where N is the size of the array, and the constant is of the order d!. We also obtain a similar algorithm for the dual tiling problem, where the goal is to compute a tiling of weight at most W using as few tiles as possible. Our algorithm yields an approximation factor (2d + 1).We implemented our algorithm and ran simulation tests on multidimensional arrays with random data. In our limited experiments, the algorithm always produced approximations that were no worse than factor two from the optimal.     

Rectangular tileability and complementary tileability are undecidable

Does a given set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.     

Counting polyominoes: Yet another attack

A polyomino is a connected collection of squares on an unbounded chessboard. There is no known formula yielding the number of distinct polyominoes of a given number of squares A polyomino enumeration method, faster than any previous, is presented. This method includes the calculation of the number of symmetric polyominoes. All polyominoes containing up to 24 squares have been enumerated (using ten months of computer time). Previously, only polyominoes up to size 18 were enumerated.     

离散几何的两个铺砌问题

利用图论和代数的方法研究离散几何中的两个铺砌问题:1)给出1×2长方形铺砌多米诺骨牌的充分必要条件;2)对高维空间盒子的情形,给出m_1×m_2×…×m_n砖能够铺砌a_1×a_2×…×a_n盒子的一些必要条件和充要条件.     

Major index for 01-fillings of moon polyominoes

We propose a major index statistic on 01-fillings of moon polyominoes which, when specialized to certain shapes, reduces to the major index for permutations and set partitions. We consider the set F(M,s;A) of all 01-fillings of a moon polyomino M with given column sum s whose empty rows are A, and prove that this major index has the same distribution as the number of north-east chains, which are the natural extension of inversions (resp. crossings) for permutations (resp. set partitions). Hence our result generalizes the classical equidistribution results for the permutation statistics inv and maj. Two proofs are presented. The first is an algebraic one using generating functions, and the second is a bijection on 01-fillings of moon polyominoes in the spirit of Foata's second fundamental transformation on words and permutations.     

Groups isomorphic to all their non-trivial normal subgroups

A finite collectionP of finite sets tiles the integers iff the integers can be expressed as a disjoint union of translates of members ofP. We associate with such a tiling a doubly infinite sequence with entries fromP. The set of all such sequences is a sofic system, called a tiling system. We show that, up to powers of the shift, every shift of finite type can be realized as a tiling system. Some of this work was done at the Mathematical Sciences Research Institute (MSRI), where research is supported in part by NSF grant DMS-9701755. The first two authors thank K. Schmidt for useful conversations and ideas.     

Triangulations (tilings) and certain block triangular matrices

For a convex polygonP withn sides, a ‘partitioning’ ofP inton−2 nonoverlapping triangles each of whose vertices is a vertex ofP is called a triangulation or tiling, and each triangle is a tile. Each tile has a given cost associated with it which may differ one from another. This paper considers the problem of finding a tiling ofP such that the sum of the costs of the tiles used is a minimum, and explores the curiosity that (an abstract formulation of) it can be cast as a linear program. Further the special structure of the linear program permits a recursive O(n ³) algorithm. Research and reproduction of this report were partially supported by the National Science Foundation Grants MCS-8119774, MCS-7926009 and ECS-8012974; Department of Energy Contract DE-AM03-76SF00326, PA# DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and donot necessarily reflect the views of the above sponsors.     

Characterization of Planar Pseudo-Self-Similar Tilings

A pseudo-self-similar tiling is a hierarchical tiling of Euclidean space which obeys a nonexact substitution rule: the substitution for a tile is not geometrically similar to itself. An example is the Penrose tiling drawn with rhombi. We prove that a nonperiodic repetitive tiling of the plane is pseudo-self-similar if and only if it has a finite number of derived Vorono\"{\i} tilings up to similarity. To establish this characterization, we settle (in the planar case) a conjecture of E. A. Robinson by providing an algorithm which converts any pseudo-self-similar tiling of R ² into a self-similar tiling of R ² in such a way that the translation dynamics associated to the two tilings are topologically conjugate. Received June 20, 2000, and in revised form January 25, 2001. Online publication July 25, 2001.     

黑白顶点数目相等的无完美匹配四角系统

四角系统是一个二部图，二部图有完美匹配的一个必要条件是对其顶点进行正常着色后，两个色类所含的顶点数相等，然而这一条件并不充分，本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14，并且只有3种非同构的形状，由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状，它们的数目分别是22与155。     

Polyominoes tiling by a genetic algorithm

Most existing placement algorithms were designed to handle blocks that are rectangular in shape. In this paper, we show how a genetic algorithm (GA) is used to construct an optimal arrangement of two-dimensional rectilinear blocks. Our approach does not require the orientation of each block to be fixed. To transform the placement problem to a GA problem, we devised a decoding technique known as circular placement. The novelty of the circular placement technique is that it configures the rectilinear blocks by building up potentially good groupings of blocks starting from the corners of the placement area. To complement the circular placement approach, we present a methodology for deriving a suitable objective function. We confirm the performance of our GA-based placement algorithm by presenting simulation results of some problems on tiling with up to 128 polyominoes. The algorithm described in this paper has great potential for applications in packing, compacting and general component placement in the various disciplines of engineering.