Search

In this article we solve the tiling problem for hyperbolic and Euclidean regular polygons whose edges are notched with matching bumps and nicks.

In this paper, we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size-bound parameters, we want to find a set of tiles of maximum total weight such that each tiles satisfies the size bounds. A solution to this problem is important to a number of computational biology applications such as selecting genomic DNA fragments for PCR-based amplicon microarrays and performing homology searches with long sequence queries. Our goal is to design efficient algorithms with linear or near-linear time and space in the normal range of parameter values for these problems. For this purpose, we first discuss the solution to a basic online interval maximum problem via a sliding-window approach and show how to use this solution in a nontrivial manner for many of the tiling problems introduced. We also discuss NP-hardness results and approximation algorithms for generalizing our basic tiling problem to higher dimensions. Finally, computational results from applying our tiling algorithms to genomic sequences of five model eukaryotes are reported.

� AND R. DANIELMAULDIN † Abstract. WesurveysomeresultsandproblemsarisingfromaclassicproblemofSteinhaus: IsthereasubsetSof R 2 suchthateachisometriccopyof Z 2 (thelatticepointsintheplane) meetsSinexactlyonepoint. §1. Introduction. We survey in this paper some of the known results, methods, and open questions concerningSteinhaus sets. Although this is primarilyasurveyarticle,weincludeafewnewresultssuchastheexistence of Steinhaus sets for certain other rectangular lattices, e.g., theorem 2.11. ThenotionofaSteinhaussetcanbeintroducedatvariouslevelsofgenerality. SteinhausaskedinthelatefiftiesiftherecouldbeasetS ⊆ R 2 suchthatS meetseveryisometriccopyoftheintegerlattice Z × Zinexactlyonepoint. WeareaskingthisquestioninthecontextofZFC,thatis,assumingchoice, but the question remains interesting in the context of ZF as well. Also, the question can be immediately extended to higher dimensionsand other lattices. Thus, ifL ⊆ R m is a lattice andn ≥m, we can ask if there is a setS ⊆ R n whichmeetseveryð(L)isexactlyonepoint,whereð: R n → R n is an isometry (and we view R m ⊆ R n in the usual way). This will be the contextformostofthediscussionofthispaper,andwewillinfactgenerally havem=n. Inthiscase,werefertosuchasetS,ifitexists,asaSteinhaus setforthelatticeL. LetuscommentthatSteinhaus'questionconcernsthe existence of a "simultaneous tiling" of the plane. To say a setE tiles the plane means the translates ofE by the lattice points in Z 2 partitions the plane. So,SisaSteinhaussetifandonlyifeachrotatedcopyofStiles R 2 . Wecangeneralizethebasicnotionsconsiderably. Given(X, A,f),where X is a set, A ⊆ P(X) is a family of subsets ofX, andf: A →CARD is

The MAX–MIN tiling problem is as follows. We are given A [1,…,n][1,…,n] , a two-dimensional array where each entry A [i][j] stores a non-negative number. Define a tile of A to be a subarray A [l,…,r][t,…,b] of A , the weight of a tile to be the sum of all array entries in it, and a tiling of A to be a collection of tiles of A such that each entry A [i][j] is contained in exactly one tile. Given a weight bound W the goal of our MAX–MIN tiling problem is to find a tiling of A such that: (1) each tile is of weight at least W (the MIN condition), and (2) the number of tiles is maximized (the MAX condition). The MAX–MIN tiling problem is known to be NP-hard; here, we present first non-trivial approximations algorithms for solving it.

Recently, using Fourier transform methods, it was shown that there is no measurable Steinhaus set in R 3 , a set which no matter how translated and rotated contains exactly one integer lattice point. Here, we show that this argument cannot generalize to any lattice and, on the other hand, give some lattices to which this method applies. We also show there is no measurable Steinhaus set for a special honeycomb lattice, the standard tetrahedral lattice in R 3 .

In this paper, we consider spin systems in three spatial dimensions, and prove that the local Hamiltonian problem for 3D lattices with face-centered cubic unit cells, 4-local translationally-invariant interactions between spin-3/2 particles and open boundary conditions is QMAEXP-complete. We go beyond a mere embedding of past hard 1D history state constructions, and utilize a classical Wang tiling problem as binary counter in order to translate one cube side length into a binary description for the verifier input. We further make use of a recently-developed computational model especially well-suited for history state constructions, and combine it with a specific circuit encoding shown to be universal for quantum computation. These novel techniques allow us to significantly lower the local spin dimension, surpassing the best translationally-invariant result to date by two orders of magnitude (in the number of degrees of freedom per coupling). This brings our models en par with the best non-translationally-invariant construction., 20 pages. 3 figures in main text; with technical appendix

International audience; Particles and collisions are convenient construction tools to compute inside tilings and enforce complex sets of tilings with simple tilesets. Locally enforceable particles being incompatible with expansivity in the orthogonal direction, a compromise has to be found to combine both notions in a same tileset. This paper introduces knight tiles: a framework to construct 4-way deterministic tilings, that is tilings completely determined by any infinite diagonal of tiles, for which local particles and collisions with many slopes can still be constructed while being expansive in infinitely many directions. The framework is then illustrated by an elegant yet simple construction to mark a diagonal with a 4-way deterministic knight tileset.

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 d+32, for d?2. The algorithm can be implemented to run in worst-case time O(N+plogN) 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.

have the same numerator. These fractions simplify to 1 a3993 and 103993 respectively. _T3_102 355 In this paper, we provide a combinatorial interpretation for the numerators and denominators of continued fractions which makes this reversal phenomenon easy to see. Through the use of counting arguments, we illustrate how this and other important identities involving continued fractions can be easily visualized, derived, and remembered. We begin by defining some basic terminology. Given an infinite sequence of integers ao ? 0, a, ? 1, a2 ? 1,. let [ao, a n.a,] denote the finite continued fraction

The tiling problem is a typical NP-complete problem, where the polyominoes are to be arranged without a gap on a finite checkerboard. In this study, the arrangement of l polyominoes on an m ×n checkerboard is considered. As the first step, the conventional parallel algorithm using the maximum neural network is verified. Then, the authors propose a solution procedure for the tiling problem, where the analog neural network is used in addition to the fitting function. Lastly, the proposed method and the conventional method are compared, and it is shown that the proposed method is also effective for more complex tiling problems. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 83(2): 1–10, 2000

Several results are proved related to a question of Steinhaus: is there a set E ⊂ℝ 2 such that the image of E under each rigid motion of IR2 contains exactly one lattice point? Assuming measurability, the analogous question in higher dimensions is answered in the negative, and on the known partial results in the two dimensional case are improved on. Also considered is a related problem involving finite sets of rotations.

We consider the assembly of a three dimensional (3D) structure by a team of heterogeneous robots capable of online sensing and error correction during the assembly process. The automated assembly problem is posed as a general 3D tiling problem where the assembly components/tiles consist of various shapes and sizes. For a desired 3D structure, we first compute the partition of the assembly strategy into N c sub-components that can be executed in parallel by a team of N c assembly robots. To enable online error detection and correction during the assembly process, mobile robots equipped with visual depth sensors are tasked to scan, identify, and track the state of the structure. The objective is to enable online detection of missing assembly components and reassignment of these components to the team of assembly robots. We present the development of the planning, sensing, and control strategies employed and report on the experimental validation of these strategies using our multi-robot testbed.

Deciding if a given set of Wang tiles admits a tiling of the plane is decidable if the number of Wang tiles (or the number of colors) is bounded, for a trivial reason, as there are only finitely many such tilesets. We prove however that the tiling problem remains undecidable if the difference between the number of tiles and the number of colors is bounded by 43. One of the main new tool is the concept of Wang bars, which are equivalently inflated Wang tiles or thin polyominoes., Comment: In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498

3D modeling reconstruction from contours is an important problem in 3D visualization. At present, many approaches are proposed to solve this problem, but these approaches can not satisfactorily solve 3D modeling reconstruction based on the complex and poor transitional contours with special occupational demand. In this paper, we propose a new interactive method to solve this complex problem which based on the present approaches. The new approach use control line to solve complex tiling problem and use assistant branching information, like point, curve and face, to solve branching problem. The new approach are applied in 3D geologic body modeling with complex ore contours. The result of the application show that the new approach can control the model more flexibility when dispose complex contours.

We study the expressibility problem: given a finite constraint language Γ on a finite domain and another relation R, can Γ express R? We prove, by an explicit family of examples, that the standard witnesses to expressibility and inexpressibility (gadgets/formulas/conjunctive queries and polymorphisms respectively) may be required to be exponentially larger than the instances. We also show that the full expressibility problem is co-NEXPTIME-hard. Our proofs hinge on a novel interpretation of a tiling problem into the expressibility problem.

In this paper, we investigate tilings of tori and rectangles with rectangular tiles. We present necessary and sufficient conditions for the existence of an integer C such that any torus, having dimensions greater than C, is tiled with two given rectangles (C depending on the dimensions of the tiles). We also give sufficient conditions to tile a sufficiently large n-dimensional rectangle with a set of (n-dimensional) rectangular tiles. We do this by combining the periodicity of some particular tilings and results concerning the so-called Frobenius number.

We investigate fragments of Halpern-Shoham's interval logic HS involving the modal operators for the relations of left or right overlap of intervals. We prove that most of these fragments are undecidable, by employing a non-trivial reduction from the octant tiling problem.

In this paper, we consider the periodic tiling problem which was proved undecidable in the Euclidean plane by Yu. Gurevich and I. Koriakov, see [3]. Here, we prove that the same problem for the hyperbolic plane is also undecidable.

Interval temporal logics are based on temporal structures where time intervals, rather than time instants, are the primitive ontological entities. They employ modal operators corresponding to various relations between intervals, known as Allen’s relations. Technically, validity in interval temporal logics translates to dyadic second-order logic, thus explaining their complex computational behavior. The full modal logic of Allen’s relations, called HS, has been proved to be undecidable by Halpern and Shoham under very weak assumptions on the class of interval structures, and this result was discouraging attempts for practical applications and further research in the field. A renewed interest has been recently stimulated by the discovery of interesting decidable fragments of HS. This paper contributes to the characterization of the boundary between decidability and undecidability of HS fragments. It summarizes known positive and negative results, it describes the main techniques applied so far in both directions, and it establishes a number of new undecidability results for relatively small fragments of HS.

In this paper, we distinguish two levels for the plane-filling property. We consider a simple and a strong one. In this paper, we give the construction which proves that the simple plane-filling property also holds for the hyperbolic plane. The plane-filling property was established for the Euclidean plane by J. Kari, see [2], in the strong version. We also give an application of the construction to devise a Peano curve in the hyperbolic plane.

In this paper, we consider the finite tiling problem which was proved undecidable in the Euclidean plane by Jarkko Kari, see [5]. Here, we prove that the same problem for the hyperbolic plane is also undecidable.

In 3D terrain reconstruction, the differences of shape and topology among contours in adjacent sections cause a difficulty as the tiling problem of branching terrain. In this paper, we present a brief and pure geometrical algorithm to reconstruct 3D terrain based on contours. The merit of our method is that the tiling rules guarantee arbitrary branching terrain can be divided into correct topology.

Simultaneous tiling for several different translational sets has been studied rather extensively, particularly in connection with the Steinhaus problem. The study of orthonormal wavelets in recent years, particularly for arbitrary dilation matrices, has led to the study of multiplicative tilings by the powers of a matrix. In this paper we consider the following simultaneous tiling problem: Given a lattice in $\L\in \R^d$ and a matrix $A\in\GLd$, does there exist a measurable set $T$ such that both $\{T+\alpha: \alpha\in\L\}$ and $\{A^nT: n\in\Z\}$ are tilings of $\R^d$? This problem comes directly from the study of wavelets and wavelet sets. Such a $T$ is known to exist if $A$ is expanding. When $A$ is not expanding the problem becomes much more subtle. Speegle \cite{Spe03} exhibited examples in which such a $T$ exists for some $\L$ and nonexpanding $A$ in $\R^2$. In this paper we give a complete solution to this problem in $\R^2$., Comment: 16 pages, no figures

A short overview of the current state in the field of quasicrystals is presented with an emphasis on the fundamental questions brought into focus by the advent of the field. Placing the research on quasicrystals in a broader context, it becomes apparent that the main questions which remain open are about the connections between the ground state structure and the interparticle interactions and between the nonequilibrium growth conditions and metastable states. From the point of view of experimental results, the main question about the structure of real quasicrystals remains unresolved.

The tiling problem is closely connected with a number of problems of information theory. We show that the Wang-Moore conjecture is valid for the one dimensional case. Namely, any set of templates which permits a tiling of the set ℤ of integers also permits a periodic tiling. We also show that any tiling of ℤ by one template is necessarily periodic. The obtained results are also valid for tiling of the set IR of real numbers.

Aperturbation of a tiling of a region inR n is a set of isometries, one applied to each tile, so that the images of the tiles tile the same region. We show that a locally finite tiling of an open region inR 2 with tiles which are closures of their interiors isrigid in the following sense: any sufficiently small perturbation of the tiling must have only “earthquake”-type discontinuities, that is, the discontinuity set consists of straight lines and arcs of circles, and the perturbation near such a curve shifts points along the direction of that curve. We give an example to show that this type of rigidity does not hold inR n , forn>2. Using rigidity in the plane we show that any tiling problem with a finite number of tile shapes (which are topological disks) is equivalent to a polygonal tiling problem, i.e. there is a set of polygonal shapes with equivalent tiling combinatorics.

A tiling of the plane with polygonal tiles is said to be strict if any point common to two tiles is a vertex of both or a vertex of neither. A triangle is said to be rational if its sides have rational length. Recently R.B. Eggleton asked if it is possible to strictly tile the plane with rational triangles using precisely one triangle from each congruence class. In this paper we constructively prove the existence of such a tiling by a suitable modification of the technique suggested by Eggleton. The theory of rational points on elliptic curves, in particular, the Nagell-Lutz theorem, plays a crucial role in completing the proof.

The classic Banach Contraction Principle states that any contraction on a complete metric space has a unique fixed point. Rather than requiring that a single operator be a contraction, we consider a minimum involving a set of powers of that operator and derive fixed-point results. Ordinary analytical techniques would be extremely unwieldy, and so we develop a method for attacking this problem by considering a related problem on tiling the integers.

Many applications have a need for indexing unstructured data. It turns out that a similar ad-hoc method is being used in many of them – that of considering small particles of the data.In this paper we formalize this concept as a tiling problem and consider the efficiency of dealing with this model in the pattern matching setting.We present an efficient algorithm for the one-dimensional tiling problem, and the one-dimensional tiled pattern matching problem. We prove the two-dimensional problem is hard and then develop an approximation algorithm with an approximation ratio converging to 2. We show that other two-dimensional versions of the problem are also hard, regardless of the number of neighbors a tile has.

This paper describes a neuro-based optimization algorithm for tiling with polyominoes. First, we review the previous neuro-based parallel algorithm for the tiling problem where l/spl times/m/spl times/n maximum neural array is required for an m/spl times/n checkerboard. Next, we propose a robust neuro-based tiling algorithm using the modified energy function which includes the fitting violation function of the polyominoes and the analog neural array. Finally, we compare our algorithm with the previous one and show that our method is much more vigorous and practical for larger tiling problems.

Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average,” This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks are easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. It is shown in [1] that the Tiling problem with uniform distribution of instances has no polynominal “on average” algorithm, unless every NP-problem with every simple probability distribution has it.