Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles

We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE, and d-RPACK) studied in the literature. Most of our algorithms are highly efficient since their running times are near-linear in the sparse input size rather than in the domain size. In addition, we improve the best known approximation ratios.     

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.     

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.     

Completeness, Sections and Selections

In this paper, we develop a general approach to set-valued semi-continuous selections which is based on order-like arguments rather than on classical approximations. The approach works nice in a number of situations demonstrating the genesis of such selection properties of set-valued mappings. In particular, it allows to generalize several known results, also to get some new results about sections of set-valued mappings.      

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.     

Coverings of Graphs and Maps, Orthogonality, and Eigenvectors

Lifts of graph and map automorphisms can be described in terms of voltage assignments that are, in a sense, compatible with the automorphisms. We show that compatibility of ordinary voltage assignments in Abelian groups is related to orthogonality in certain -modules. For cyclic groups, compatibility turns out to be equivalent with the existence of eigenvectors of certain matrices that are naturally associated with graph automorphisms. This allows for a great simplification in characterizing compatible voltage assignments and has applications in constructions of highly symmetric graphs and maps.     

Bergman 穷竭, 完备与稳定性

Bergman核是国内外研究多复变函数论的一个传统课题,本文主要介绍利用超定的非齐次Cuauchy-Riemann方程组的现代Hilbert空间理论研究Bergman核的穷竭性,稳定性与Bergman度量的完备性所取得的最新进展。     

Tiling Groupoids and Bratteli Diagrams

Let T be an aperiodic and repetitive tiling of ${{\mathbb R}^d}$ with finite local complexity. Let Ω be its tiling space with canonical transversal ${\Xi}$ . The tiling equivalence relation ${R_\Xi}$ is the set of pairs of tilings in ${\Xi}$ which are translates of each others, with a certain (étale) topology. In this paper ${R_\Xi}$ is reconstructed as a generalized “tail equivalence” on a Bratteli diagram, with its standard AF -relation as a subequivalence relation. Using a generalization of the Anderson–Putnam complex (Bellissard et al. in Commun. Math. Phys. 261:1–41, 2006) Ω is identified with the inverse limit of a sequence of finite CW-complexes. A Bratteli diagram ${{\mathcal B}}$ is built from this sequence, and its set of infinite paths ${\partial {\mathcal B}}$ is homeomorphic to ${\Xi}$ . The diagram ${{\mathcal B}}$ is endowed with a horizontal structure: additional edges that encode the adjacencies of patches in T. This allows to define an étale equivalence relation ${R_{\mathcal B}}$ on ${\partial {\mathcal B}}$ which is homeomorphic to ${R_\Xi}$ , and contains the AF-relation of “tail equivalence”.     

Tiling Space by Platonic Solids, I

There exist precisely 914, 58, and 46 equivariant types of tile-transitive tilings of three-dimensional euclidean space by topological cubes, octahedra, and tetrahedra, that fall into 11, 3, and 9 topological families, respectively. Representatives are described for all topological families. A general method for obtaining results of this kind is introduced. Received February 13, 1997, and in revised form September 17, 1997.     

Completeness,Compactness, Effective Dimensions

We investigate a directed metric on the space of infinite binary sequences defined by where C(X?n‖Y?n) is the Kolmogorov complexity of X?n given Y?n. In particular we focus on the topological aspects of the associated metric space—proving that it is complete though very far from being compact. This is a continuation of earlier work investigating other geometrical and toplogical aspects of this metric.     

Orthogonality and Hecke operators

In this article we analyze orthogonality relations between old forms and the connection to the theory of Hecke operators.     

Projections,Birkhoff Orthogonality and Angles in Normed Spaces

Let X be a Minkowski plane, i.e., a real two dimensional normed linear space. We use projections to give a definition of the angle Aq（x, y） between two vectors x and y in X, such that x is Birkhoff orthogonal to y if and only if Aq（x,y）=π/2. Some other properties of this angle are also discussed.     

One-dimensional Tiling Semigroups

We investigate the structure of Kellendonks tiling semigroup in the case of 1-dimensional tilings.     

Self-Similar Tiling Systems,Topological Factors and Stretching Factors

In this paper we prove that if two self-similar tiling systems, with respective stretching factors λ ₁ and λ ₂, have a common factor which is a nonperiodic tiling system, then λ ₁ and λ ₂ are multiplicatively dependent.     

Projections,Birkhoff Orthogonality and Angles in Normed Spaces

Let $X$ be a Minkowski plane, i.e., a real two dimensional normed linear space. We use projections to give a definition of the angle $A_q(x, y)$ betweentwo vectors $x$ and $y$ in $X$, such that $x$ is Birkhoff orthogonal to $y$ if and only if $A_q(x, y) =frac{π}{2}$. Some other properties of this angle are also discussed.     

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.     

Generalized Analytic Spaces, Completeness and Fragmentability

Classical analytic spaces can be characterized as projections of Polish spaces. We prove analogous results for three classes of generalized analytic spaces that were introduced by Z. Frolik, D. Fremlin and R. Hansell. We use the technique of complete sequences of covers. We explain also some relations of analyticity to certain fragmentability properties of topological spaces endowed with an additional metric.     

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 Infinite-Dimensional Normed Spaces

The present paper deals with real infinite-dimensional normedspaces; some of the main concepts here make sense, and havebeen treated in the literature, in the general context of topologicalHausdorff linear spaces over reals. A subset of a normed space X is a body if it is different fromX itself and is the closure of its non-empty interior. A coveringof X by bodies is called a tiling of X whenever any two differentmembers of it have disjoint interiors. The elements of sucha covering are called tiles. A tiling is bounded (respectivelyconvex) whenever each tile is bounded (respectively convex).1991 Mathematics Subject Classification 46B20.