Tiling space and slabs with acute tetrahedra

We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 74.21°, and another which tiles a slab in space.     

Tiling the torus and other space forms

We consider graphs on two-dimensional space forms which are quotient graphs /F, where is an infinite, 3-connected, face, vertex, or edge transitive planar graph andF is a subgroup of Aut(), all of whose elements act freely on . The enumeration of quotient graphs with transitivity properties reduces to computing the normalizers in Aut() of the subgroupsF. Results include: all isogonal toriodal polyhedra belong to the two families found by Grünbaum and Shephard; there are no transitive graphs on the Möbius band; there is a graph on the Klein bottle whose automorphism group acts transitively on its faces, edges, and vertices.This paper is an expanded version of a lecture presented to the Conference on Combinatorial Geometry, Oberwolfach, Germany, September 1984.     

Tiling Bricks with Bricks

The problem addressed by the paper is the filling of a large brick with replicas of smaller bricks of different sizes. We solve this problem by reducing it to an algebraic problem about polynomials. As a by-product, we obtain new combinatorial interpretations of the connection constants linking some classical polynomial sequences of combinatorics.     

Tiling polygons with parallelograms

Under what conditions can a simple polygon be tiled by parallelograms? In this paper we give matching necessary and sufficient conditions on the polygon to be tilable and characterize the set of possible tilings. We also provide an efficient algorithm for constructing a tiling.     

Tiling Polygons with Lattice Triangles

Given a simple polygon with rational coordinates having one vertex at the origin and an adjacent vertex on the x-axis, we look at the problem of the location of the vertices for a tiling of the polygon using lattice triangles (i.e., triangles which are congruent to a triangle with the coordinates of the vertices being integer). We show that the coordinates of the vertices in any tiling are rationals with the possible denominators odd numbers dependent on the cotangents of the angles in the triangles.     

Tiling simply connected regions with rectangles

In 1995, Beauquier, Nivat, Rémila, and Robson showed that tiling of general regions with two bars is NP-complete, except for a few trivial special cases. In a different direction, in 2005, Rémila showed that for simply connected regions by two rectangles, the tileability can be solved in quadratic time (in the area). We prove that there is a finite set of at most 10⁶ rectangles for which the tileability problem of simply connected regions is NP-complete, closing the gap between positive and negative results in the field. We also prove that counting such rectangular tilings is #P-complete, a first result of this kind.     

Hard Tiling Problems with Simple Tiles

It is well known that the question of whether a given finite region can be tiled with a given set of tiles is NP -complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process we show that Monotone 1-in-3 Satisfiability is NP -complete for planar cubic graphs. In higher dimensions we show NP -completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply connected regions on the four-dimensional hypercubic lattice. Received March 8, 2000, and in revised form May 14, 2001, and June 18, 2001. Online publication October 12, 2001.     

Tiling Hamming Space with Few Spheres

We show that if the collection of all binary vectors of lengthnis partitioned intokspheres, then eitherk2 orkn+2. Moreover, such partitions withk=n+2 are essentially unique.     

Tiling Lattices with Sublattices,I

Call a coset C of a subgroup of Z^d{\bf Z}^{d} a Cartesian coset if C equals the Cartesian product of d arithmetic progressions. Generalizing Mirsky–Newman, we show that a non-trivial disjoint family of Cartesian cosets with union Z^d{\bf Z}^{d} always contains two cosets that differ only by translation. Where Mirsky–Newman’s proof (for d=1) uses complex analysis, we employ Fourier techniques. Relaxing the Cartesian requirement, for d>2 we provide examples where Z^d{\bf Z}^{d} occurs as the disjoint union of four cosets of distinct subgroups (with one not Cartesian). Whether one can do the same for d=2 remains open.     

铺瓷砖问题的推广

铺瓷砖问题是数学模型中著名的问题,在研究了铺瓷砖问题的基础上,对其进行了推广,并给出了各种推广情形的结果.     

Tiling a Polygon with Two Kinds of Rectangles

We fix two rectangles with integer dimensions. We give a quadratic time algorithm which, given a polygon F as input, produces a tiling of F with translated copies of our rectangles (or indicates that there is no tiling). Moreover, we prove that any pair of tilings can be linked by a sequence of local transformations of tilings, called flips. This study is based on the use of Conway’s tiling groups and extends the results of Kenyon and Kenyon (limited to the case when each rectangle has a side of length 1).     

Tiling Convex Polygons with Congruent Equilateral Triangles

We study the sets $\mathcal{T}_{v}=\{m \in\{1,2,\ldots\}: \mbox{there is a convex polygon in }\mathbb{R}^{2}\mbox{ that has }v\mbox{ vertices and can be tiled with $m$ congruent equilateral triangles}\}$ , v=3,4,5,6. $\mathcal{T}_{3}$ , $\mathcal{T}_{4}$ , and $\mathcal{T}_{6}$ can be quoted completely. The complement $\{1,2,\ldots\} \setminus\mathcal{T}_{5}$ of $\mathcal{T}_{5}$ turns out to be a subset of Euler’s numeri idonei. As a consequence, $\{1,2,\ldots\} \setminus\mathcal{T}_{5}$ can be characterized with up to two exceptions, and a complete characterization is given under the assumption of the Generalized Riemann Hypothesis.     

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.     

Some Generalizations of the Pinwheel Tiling

We introduce a new family of nonperiodic tilings, based on a substitution rule that generalizes the pinwheel tiling of Conway and Radin. In each tiling the tiles are similar to a single triangular prototile. In a countable number of cases, the tiles appear in a finite number of sizes and an infinite number of orientations. These tilings generally do not meet full-edge to full-edge, but can be forced through local matching rules. In a countable number of cases, the tiles appear in a finite number of orientations but an infinite number of sizes, all within a set range, while in an uncountable number of cases both the number of sizes and the number of orientations is infinite. Received April 9, 1996, and in revised form September 16, 1996.     

Tiling R 3 with circles and disks

While it is not possible to tile R ² with circles, several constructions are known for tiling R ³ with circles or with homeomorphs of circles subject to various constraints. We extend this work on circles and obtain as well some analogous results on tiling R ² and R ³ with disks.     

Natural Tiling, Lattice Tiling and Lebesgue Measure of Integral Self-Affine Tiles

In the existing theory of self-affine tiles, one knows thatthe Lebesgue measure of any integral self-affine tile correspondingto a standard digit set must be a positive integer and everyintegral self-affine tile admits some lattice Zⁿ as a translationtiling set of Rⁿ. In this paper, we give algorithms to evaluatethe Lebesgue measure of any such integral self-affine tile Kand to determine all of the lattice tilings of Rⁿ by K. Moreover,we also propose and determine algorithmically another type oftranslation tiling of Rⁿ by K, which we call natural tiling.We also provide an algorithm to decide whether or not Lebesguemeasure of the set K (K+j), j–Zⁿ, is strictly positive.     

A Cube Tiling of Dimension Eight with No Facesharing

   Abstract. A cube tiling of eight-dimensional space in which no pair of cubes share a complete common seven-dimensional face is constructed. Together with a result of Perron, this shows that the first dimension in which such a tiling can exist is seven or eight.