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.     

Tilings of Convex Polygons with Congruent Triangles

By the spectrum of a polygon A we mean the set of triples (??,??,??) such that A can be dissected into congruent triangles of angles ??,??,??. We propose a technique for finding the spectrum of every convex polygon. Our method is based on the following classification. A tiling is called regular if there are two angles of the triangles, ?? and ?? such that at every vertex of the tiling the number of triangles having angle ?? equals the number of triangles having angle ??. Otherwise the tiling is irregular. We list all pairs (A,T) such that A is a convex polygon and T is a triangle that tiles A regularly. The list of triangles tiling A irregularly is always finite, and can be obtained, at least in principle, by considering the system of equations satisfied by the angles, examining the conjugate tilings, and comparing the sides and the area of the triangles to those of A. Using this method we characterize the convex polygons with infinite spectrum, and determine the spectrum of the regular triangle, the square, all rectangles, and the regular N-gons with N large enough.     

Tilings of Polygons with Similar Triangles, II

Let A be a polygon, and let s (A) denote the number of distinct nonsimilar triangles Δ such that A can be dissected into finitely many triangles similar to Δ . If A can be decomposed into finitely many similar symmetric trapezoids, then s(A)=∞ . This implies that if A is a regular polygon, then s(A)=∞ . In the other direction, we show that if s(A)=∞ , then A can be decomposed into finitely many symmetric trapezoids with the same angles. We introduce the following classification of tilings: a tiling is regular if Δ has two angles, α and β , such that at each vertex of the tiling the number of angles α is the same as that of β . Otherwise the tiling is irregular. We prove that for every polygon A the number of triangles that tile A irregularly is at most c ⋅ n ⁶ , where n is the number of vertices of A. If A has a regular tiling, then A can be decomposed into finitely many symmetric trapezoids with the same angles. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p411.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 17, 1997, and in revised form June 16, 1997.     

A Double Tiling of Triangles and Regular Hexagons

A tiling of triangles and regular hexagons, which wraps around a focal point and covers the plane twice, is investigated using both synthetic triangle geometry and complex numbers. Received February 12, 1999, and in revised form October 25, 1999. Online publication May 16, 2000.     

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.     

Enumeration of Almost-Convex Polygons on the Square Lattice

We classify self-avoiding polygons on the square lattice according to a concavity measure, m, where 2m is the difference between the number of steps in the polygon and the perimeter of the minimal rectangle bounding the polygon. We generate series expansions for the perimeter generating functions S_m(x) for polygons of concavity m. We analyze the series S_m(x) for m = 0 to 3. If N_m,n denotes the number of polygons of perimeter 2n and concavity m, with m = o(n^1/2), we prove that N_m,n ? 2^2n?m?7n^m+1/m!, and that the radius of convergence of the series counting all polygons with m = o(n) is equal to 1/4. Our numerical data leads us to conjecture that in fact for m = o(n^1/2), a result confirmed for m = 0 and 1.     

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.     

Triangles with Three Rational Medians

We present a characterization of all rational sided triangles with three rational medians. It turns out that they each correspond to a point on a one-parameter family of elliptic curves. It is possible to show that the rank of this family is at least two and in fact some reasonably high rank curves appear among them.     

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

Indecomposable Coverings with Concave Polygons

We show that for any concave polygon that has no parallel sides and for any k, there is a k-fold covering of some point set by the translates of this polygon that cannot be decomposed into two coverings. Moreover, we give a complete classification of open polygons with this property. We also construct for any polytope (having dimension at least three) and for any k, a k-fold covering of the space by its translates that cannot be decomposed into two coverings.     

Extremal Polygons with Minimal Perimeter

In this paper we will investigate an isoperimetric type problem in lattices. If K is a bounded O-symmetric (centrally symmetric with respect to the origin) convex body in En of volume v(K) = 2n det L which does not contain non-zero lattice points in its interior, we say that K is extremal with respect to the given lattice L. There are two variations of the isoperimetric problem for this class of polyhedra. The first one is: Which bodies have minimal surface area in the class of extremal bodies for a fixed n-dimensional lattice? And the second one is: Which bodies have minimal surface area in the class of extremal bodies with volume 1 of dimension n? We characterize the solutions of these two problems in the plane. There is a consequence of these results, the solutions of the above problems in the plane give the solution of the lattice-like covering problem: Determine those centrally symmetric convex bodies whose translated copies (with respect to a fixed lattice L) cover the space and have minimal surface area.

     

Polygons with Parallel Opposite Sides

In this paper we consider convex planar polygons with parallel opposite sides. These polygons can be regarded as discretizations of closed convex planar curves by taking tangent lines at samples with pairwise parallel tangents. For such polygons, we define discrete versions of the area evolute, central symmetry set, equidistants, and area parallels and show that they behave quite similarly to their smooth counterparts.     

Spotlight Tiling

This article introduces spotlight tiling, a type of covering which is similar to tiling. The distinguishing aspects of spotlight tiling are that the “tiles” have elastic size, and that the order of placement is significant. Spotlight tilings are decompositions, or coverings, and can be considered dynamic as compared to typical static tiling methods. A thorough examination of spotlight tilings of rectangles is presented, including the distribution of such tilings according to size, and how the directions of the spotlights themselves are distributed. The spotlight tilings of several other regions are studied, and suggest that further analysis of spotlight tilings will continue to yield elegant results and enumerations.     

Monoids with Stable Torsion-Free Polygons

We deal with monoids possessing a stable class of torsion-free polygons over them.     

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.