Search

The topic of recurrence relations has recently been introduced in many discrete mathematics textbooks. Recurrence relations are efficient modelling and problem-solving techniques used in mathematic...

Several articles deal with tilings with squares and dominoes on 2-dimensional boards, but only a few on boards in 3-dimensional space. We examine a tiling problem with coloured cubes and bricks on ...

In this paper, new integer programming models of the problem of irregular polyomino tiling are introduced. We consider tiling of finite, square, NxN-sized structure with L-shaped trominoes without any restriction on their number. Each polyomino can be rotated 90\(^{\circ }\), so there are four orientations of the L-tromino. Developed models are effective for small-size instances. For medium- and large-size instances we suggest dividing the initial structure into several equally sized parts and combine the solutions of optimized tilings. We tried to apply new models to the existing information-theoretic entropy-based approach. We conducted computational experiments using IBM ILOG CPLEX package. The problem of irregular polyomino tiling can be applied to the design of phased array antennas where polyomino-shaped subarrays are used to reduce the cost of the array antenna and to reduce the undesired sidelobes radiation. Computational results along with antenna simulation results are presented in the paper.

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.

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.

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

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.