An Object Grammar for Column-Convex Polyominoes

In this paper we propose an object grammar decomposition for the classes of columnconvex, and directed column-convex polyominoes. As a consequence, we obtain the enumeration of such classes according to the semi-perimeter, thus giving a natural explanation of the fact that the generating functions of both the classes are algebraic.AMS Subject Classification: 05A15.     

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.     

The Art Gallery Theorem for Polyominoes

We explore the art gallery problem for the special case that the domain (gallery) P is an m-polyomino, a polyform whose cells are m unit squares. We study the combinatorics of guarding polyominoes in terms of the parameter m, in contrast with the traditional parameter n, the number of vertices of P. In particular, we show that $\lfloor\frac{m+1}{3} \rfloor$ point guards are always sufficient and sometimes necessary to cover an m-polyomino, possibly with holes. When $m \leq\frac{3n}{4} - 4$ , the sufficiency condition yields a strictly lower guard number than $\lfloor\frac{n}{4}\rfloor$ , given by the art gallery theorem for orthogonal polygons.     

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.     

Self-clique Helly circular-arc graphs

A clique in a graph is a complete subgraph maximal under inclusion. The clique graph of a graph is the intersection graph of its cliques. A graph is self-clique when it is isomorphic to its clique graph. A circular-arc graph is the intersection graph of a family of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. In this note, we describe all the self-clique Helly circular-arc graphs.     

A Helly Type Conjecture

A family of sets is Π ⁿ , or n -pierceable, if there exists a set of n points such that each member of the family contains at least one of them. It is Π _k ⁿ if every subfamily of size k or less is Π ⁿ . Helly's theorem is one of the fundamental results in Combinatorial Geometry. It asserts, in the special case of finite families of convex sets in the plane, that Π ₃ ¹ implies Π ¹ . However, there is no k such that Π _k ² implies 2 -pierceability for all finite families of convex sets in the plane. It is therefore natural to propose the following: Conjecture. There exists a k ₀ such that, for all planar finite families of convex sets , Π _k0 ² implies Π ³ . Proofs of this conjecture for restricted families of convex sets are discussed. Received October 8, 1996, and in revised form August 12, 1997.     

On a theorem of Helly

We consider a group of problems related to the well-known Helly theorem on the intersections of convex bodies. We introduce convex subsetsK(?) of a compact convex setK defined by the relation $$K(f) = co\left\{ {\frac{N}{{N + 1}}x + \frac{N}{{N + 1}}f(x)} \right\}{\text{ }}(x \in K \subset \mathbb{R}^N ),$$ where?: K→K are continuous mappings, and prove that the intersection ∩ _?∈F K(?) is not empty; hereF is the set of all continuous mappings?: K→K.     

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.     

Helly families of maximal size

The maximal size of a family of r-sets of a set with n elements having the Helly property of order k < r is (_r?1^n?1).     

A topological colorful Helly theorem

Let be d+1 families of convex sets in . The Colorful Helly Theorem (see (Discrete Math. 40 (1982) 141)) asserts that if for all choices of then there exists an 1?i?d+1 such that .Our main result is both a topological and a matroidal extension of the colorful Helly theorem. A simplicial complex X is d-Leray if for all induced subcomplexes Y⊂X and i?d.Theorem.LetXbe ad-Leray complex on the vertex setV. Suppose M is a matroidal complex on the same vertex setVwith rank functionρ. IfM⊂Xthen there exists a simplexτ∈Xsuch thatρ(V−τ)?d.     

A Non-expensive Homological Helly Theorem

We will discuss the following result: for a topological space X with the property that $H_k(U)=0$ for $k⩾d$ and every open subset U of X, a finite family of open sets in X has nonempty intersection if for any subfamily of size j, $1⩽j⩽d+1$, the ($d-j$)-dimensional reduced homology group of its intersection is zero. We also use this theorem to discuss new results concerning transversal affine planes to families of convex sets.     

Polyominoes Determined by Permutations: Enumeration via Bijections

A permutominide is a set of cells in the plane satisfying special connectivity constraints and uniquely defined by a pair of permutations. It naturally generalizes the concept of permutomino, recently investigated by several authors and from different points of view [1, 2, 4, 6, 7]. In this paper, using bijective methods, we determine the enumeration of various classes of convex permutominides, including, parallelogram, directed convex, convex, and row convex permutominides. As a corollary we have a bijective proof for the number of convex permutominoes, which was still an open problem.     

On Helly families of maximal size

Considering families of subsets of a given set. The families of maximal size are determined for (i) Sperner families having the Helly property of order 2; (ii) families having the Helly property of order k.