Search

The local structure of the derived tilings T of the two-dimensional torus 𝕋2 is studied. The polygonal types of stars in these tilings are classified. It is proved that in the nondegenerate case, the tilings T contain stars of seven different types, and all the types are represented by stars with interior vertices from the crown Cr of the tiling T . Also the maximum principle is established, based on which the layer-by-bayer growth algorithm for the derived tilings T is constructed. [ABSTRACT FROM AUTHOR]

The parallel efficiency is raised by increasing the locality of calculation. With the locally recursive non-locally asynchronous algorithms method, we have constructed a new algorithm that improves the locality of the cross-stencil scheme implementation by the decomposition of the 3D computational domain in time and space. The decomposition is based on a tiling of the 3D1T space into hexahedrons that closely fit the octahedron shape. This shape leads to an algorithm that is less intuitive than the rectangular domain decomposition, but since it follows the natural shape of the dependency region of the cross stencil, it has advantages in data localization and parallelization possibilities. We show its construction, analysis, and implementation possibilities. We present the benchmark results and show that the algorithm follows quantitative estimations: The performance exceeds the memory-bound limit of the stepwise implementation and does not degrade when the whole domain data do not fit higher cache levels. [ABSTRACT FROM AUTHOR]

In digital pathology, image similarity algorithms are used to find cancer in tissue cells from medical images. However, it is very difficult to apply image similarity algorithms used in general purpose system. Because in the medical field, accuracy and reliability must be perfect when looking for cancer cells by using image similarity techniques to pathology images. To cope with this problem, this paper proposes an efficient similar image search algorithm for digital pathology by applying leveling and tiling scheme on OpenSlide format. Furthermore, we apply image sync method to extract feature key points during image similarity processing. In the experiment, to prove the efficiency of the proposed system, we conduct several experiments including algorithm performance, algorithm accuracy and computation time. The experiments result shows that the proposed system efficiently retrieves similar cell images from pathology images. [ABSTRACT FROM AUTHOR]

The design of subarrayed planar phased arrays characterized by an irregular organization of domino-shaped tiles is addressed. Starting from optimal tiling theorems drawn from mathematical theory, an enumerative approach able to retrieve the optimal clustering providing the maximum aperture coverage and the best radiation performance is proposed to deal with the synthesis of low-/medium-size rectangular arrays. Based on the same optimal theorems and still exploiting the algorithmic procedures at the basis of the enumerative approach, an innovative schemata-based optimization method is introduced for designing large arrays, as well. A set of representative results, concerned with ideal as well as real radiating elements, is reported and discussed to highlight the features and the potentialities of the proposed analytically based design framework. [ABSTRACT FROM AUTHOR]

We demonstrate the potential of Kurt Bruckner's 'addition algorithm', which is based on the substitution rule for the generation of the Robinson triangle tiling, a variant of the Penrose tiling. The artist Kurt Bruckner developed his straightforward approach intuitively for the creation of quasiperiodic ornaments. This versatile method can be used for the construction of achiral, homochiral and racemic quasiperiodic ornaments, as well as for the generation of decorated two-level (two-color) Penrose tilings. Therefore, the underlying tiling is always the same kind of Penrose tiling, which is invariant under the action of specific mirror and black/white mirror operations in contrast to unit tiles that are decorated in specific ways. Compared to the underlying classical substitution method the advantage of Kurt Bruckner's approach is its simplicity and versatility for the creation of decorated tilings. Using a vector graphics editor, large and arbitrarily complex quasiperiodic ornaments can be easily generated manually. [ABSTRACT FROM AUTHOR]

Conway and Lagarias observed that a triangular region T(m) in a hexagonal lattice admits a signed tiling by three-in-line polyominoes (tribones) if and only if m ∈ {9d -- 1, 9d}d∈N? We apply the theory of Gröbner bases over integers to show that T(m) admits a signed tiling by n-in-line polyominoes (n-bones) if and only if m d∈N {dn² -- l,dn²}d∈N· Explicit description of the Gröbner basis allows us to calculate the 'Gröbner discrete volume' of a lattice region by applying the division algorithm to its 'Newton polynomial'. Among immediate consequences is a description of the tile homology group for the n-in-line polyomino. [ABSTRACT FROM AUTHOR]

Forest data acquisition, which is of crucial importance for modeling global biogeochemical cycles and climate, makes a contribution to building the ecological Digital Earth (DE). Due to the complex calculations and large volumes of data associated with high-resolution images of large areas, accurate and effective extraction of individual tree crowns remains challenging. In this study, two GeoEye-1 panchromatic images of Beihai and Ningbo in China with areas of 5 and 25 km2, respectively, were used as experimental data to establish a novel method for the automatic extraction of individual tree crowns based on a self-adaptive mutual information (SMI) algorithm and tile computing technology (SMI-TCT). To evaluate the performance of the algorithm, four commonly used algorithms were also applied to extract the individual tree crowns. The overall accuracy of the proposed method for the two experimental areas was superior to that of the four other algorithms, with maximum extraction accuracies of 85.7% and 63.8%. Moreover, the results also indicated that the novel method was suitable for individual tree crowns extraction in sizeable areas because of the multithread parallel computing technology. [ABSTRACT FROM AUTHOR]

In this paper, our results on algorithmic analysis of tiling in hyperbolic spaces are discussed. We overview results and developments obtained by the approach, focusing on the construction of universal cellular automata in hyperbolic spaces with a minimal number of cell states. [ABSTRACT FROM AUTHOR]

We introduce a bichromatic Delaunay quadrangulation principle by assigning the vertices of a Delaunay triangulation one of two colors, then discarding edges between vertices of the same color. We present algorithms for generating quadrangulations using this principle and simple refinements. The global vertex coloring ensures that only local refinements are needed to get all quads. This is in contrast to triangle-pairing algorithms, which get stuck with isolated triangles that require global refinement. We present two new sphere-packing algorithms for generating the colored triangulation, and we may also take as input a Delaunay refinement mesh and color it arbitrarily. These mesh non-convex planar domains with provable quality: quad angles in [10o,174o] and edges in [0.1, 2] r . The algorithms extend to curved surfaces and graded meshes. The “random” algorithm generates points with blue noise. The “advancing-front” algorithm produces large patches of boundary-aligned square tilings. [ABSTRACT FROM AUTHOR]

We describe an algorithm to compute the Tutte polynomial of large fragments of Archimedean tilings by squares, triangles, hexagons and combinations thereof. Our algorithm improves a well known method for computing the Tutte polynomial of square lattices. We also address the problem of obtaining Tutte polynomial evaluations from the symbolic expressions generated by our algorithm, improving the best known lower bound for the asymptotics of the number of spanning forests, and the lower and upper bounds for the asymptotics of the number of acyclic orientations of the square lattice. [ABSTRACT FROM AUTHOR]

Simulating multiple character interaction is challenging because character actions must be carefully coordinated to align their spatial locations and synchronized with each other. We present an algorithm to create a dense crowd of virtual characters interacting with each other. The interaction may involve physical contacts, such as hand shaking, hugging, and carrying a heavy object collaboratively. We address the problem by collecting deformable motion patches, each of which describes an episode of multiple interacting characters, and tiling them spatially and temporally. The tiling of motion patches generates a seamless simulation of virtual characters interacting with each other in a nontrivial manner. Our tiling algorithm uses a combination of stochastic sampling and deterministic search to address the discrete and continuous aspects of the tiling problem. Our tiling algorithm made it possible to automatically generate highly complex animation of multiple interacting characters. We achieve the level of interaction complexity far beyond the current state of the art that animation techniques could generate, in terms of the diversity of human behaviors and the spatial/temporal density of interpersonal interactions. [ABSTRACT FROM PUBLISHER]

We present a novel algorithm for generating a planar parameterization of the region surrounding a curve embedded in a 3D surface, which we call a stroke parameterization. The technique, which extends the well-known Discrete Exponential Map [SGW06], uses the same basic geometric transformations and hence is both efficient and easy-to-implement. We also handle self-intersecting curves, for which a 1-1 map between the original surface and the plane is not possible. Stroke parameterizations provide an ideal coordinate space for solving a variety of computer graphics problems. We present applications including tiling texture and displacement along 3D brush strokes, procedural texturing along 3D paths, and user-guided crease extraction. [ABSTRACT FROM AUTHOR]

High-symmetry free tilings of the two-dimensional hyperbolic plane () can be projected to genus-3 3-periodic minimal surfaces (TPMSs). The three-dimensional patterns that arise from this construction typically consist of multiple catenated nets. This paper presents a construction technique and limited catalogue of such entangled structures, that emerge from the simplest examples of regular ribbon tilings of the hyperbolic plane via projection onto four genus-3 TPMSs: the P, D, G(yroid) and H surfaces. The entanglements of these patterns are explored and partially characterized using tools from TOPOS, GAVROG and a new tightening algorithm. [ABSTRACT FROM AUTHOR]

Cluster analysis of 194 tetrahedral T structures of zeolites has been performed by the tiling method using the TOPOS program package. An algorithm of the complete expansion of T structures in tiles (complementarily bound polyhedral clusters, which are responsible for the normal (face-to-face) partition of crystal space) and an algorithm for selecting nonintersecting tiles were used. Primary tiles, which number no more than two for any zeolite studied and have packing that completely determines the topology of the entire zeolite structure, have been determined for 41 zeolites. It is established that 24 zeolites are characterized by a single assembly version, 15 have two alternative versions, and IWR and TSC zeolites are characterized by 3 and 4 assembly versions. Isolated zeolites contain 2-11 topologically different T tiles, where n is the number of tetrahedral T sites per tile; n = 4-168 and the diameter is 6-35 Å. The most numerous group of zeolites is characterized by n values of 4-18. This group contains no tiles with the odd values n = 7-17 and even value n = 6. The other group includes zeolites with large n values: 24, 30, 32, 36, 42, 48, 64, 72, 96, and 168. [ABSTRACT FROM AUTHOR]

This Rapid Communication presents a stochastic Wang tiling-based technique to compress or reconstruct disordered microstructures on the basis of given spatial statistics. Unlike the existing approaches based on a single unit cell, it utilizes a finite set of tiles assembled by a stochastic tiling algorithm, thereby allowing to accurately reproduce long-range orientation orders in a computationally efficient manner. Although the basic features of the method are demonstrated for a two-dimensional particulate suspension, the present framework is fully extensible to generic multidimensional media. [ABSTRACT FROM AUTHOR]

Abstract: We prove that the number of monomer-dimer tilings of an square grid, with monomers in which no four tiles meet at any point is , when m and n have the same parity. In addition, we present a new proof of the result that there are such tilings with n monomers, which divides the tilings into n classes of size . The sum of these tilings over all monomer counts has the closed form and, curiously, this is equal to the sum of the squares of all parts in all compositions of n. We also describe two algorithms and a Gray code ordering for generating the tilings with n monomers, which are both based on our new proof. [Copyright &y& Elsevier]

We propose the use of large tree-structured dictionaries of tilings for video compression. Our first contribution is the construction of a rate-distortion cost function that admits fast search algorithms to select the optimal tiling for the motion compensation stage of a video coder. The computation of the cost is enabled through novel algorithms to approximate the bit rate and the distortion. Our second contribution is an efficient arithmetic coding algorithm to encode the selected tree-structured tiling. We illustrate the effectiveness of our approach by showing that a H.264/AVC-like video coder utilizing one of the proposed tiling selection methods results in up to 16% savings in bit rate for several standard video sequences as compared to H.264/AVC. This is accomplished with only a modest increase in the computation time at the encoder. [ABSTRACT FROM AUTHOR]

Self-assembly is a powerful process found in nature that guides simple objects assembling, on their own, into complex structures. Self-assembly is of interest to computer scientists because self-assembling systems can compute functions, assemble shapes, and guide distributed robotics systems. The tile assembly model is a formal mathematical model of self-assembly that allows the study of time and space complexities of self-assembling systems that lie at the heart of several molecular computer implementations and distributed computational software systems. These implementations and systems require efficient tile systems with small tilesets and fast execution times. The state of the art, however, requires vastly complex tile systems with large tilesets to implement fast algorithms. In this paper, I present $${\mathbb{S}}_{FS},$$ a tile system that decides 3- SAT by creating $$O^{\star}(1.8393^n)$$ nondeterministic assemblies in parallel, improving on the previous best known solution that requires $$\Uptheta(2^n)$$ such assemblies. This solution directly improves the feasibility of building molecular 3- SAT solvers and efficiency of distributed software. I formally prove the correctness of the system, the number of required parallel assemblies, that the size of the system's tileset is $$147 = \Uptheta(1),$$ and that the assembly time is nondeterministic linear in the size of the input. [ABSTRACT FROM AUTHOR]

We introduce a hierarchical self assembly algorithm that produces the quasiperiodic patterns found in the Robinson tilings and suggest a practical implementation of this algorithm using DNA origami tiles. We modify the abstract Tile Assembly Model (aTAM), to include active signaling and glue activation in response to signals to coordinate the hierarchical assembly of Robinson patterns of arbitrary size from a small set of tiles according to the tile substitution algorithm that generates them. Enabling coordinated hierarchical assembly in the aTAM makes possible the efficient encoding of the recursive process of tile substitution. [ABSTRACT FROM AUTHOR]

We describe computer algorithms that produce the complete set of isohedral tilings by n-omino or n-iamond tiles in which the tiles are fundamental domains and the tilings have 3-, 4-, or 6-fold rotational symmetry. The symmetry groups of such tilings are of types p3, p31m, p4, p4g, and p6. There are no isohedral tilings with p3m1, p4m, or p6m symmetry groups that have polyominoes or polyiamonds as fundamental domains. We display the algorithms' output and give enumeration tables for small values of n. This expands earlier works [1,2] and is a companion to [3]. [ABSTRACT FROM AUTHOR]

Tiling recognizable two-dimensional languages, also known as REC, generalize recognizable string languages to two dimensions and share with them several theoretical properties. Nevertheless family REC is not closed under complementation and this implies that it is intrinsically non-deterministic. We consider different notions of unambiguity and determinism and the corresponding REC subclasses: they define a hierarchy inside REC. We show that some definitions of unambiguity are equivalent to particular notions of determinism and therefore the corresponding classes have linear parsing algorithms and are closed under complementation. [ABSTRACT FROM AUTHOR]

Quasicrystals are characterized by the diffraction patterns which consist of pure bright peaks. Substitution tilings are commonly used to obtain geometrical models for quasicrystals. We consider certain substitution tilings and show how to determine a quasicrystalline structure for the substitution tilings computationally. In order to do this, it is important to have the Meyer property on the substitution tilings. We use the recent result of Lee and Solomyak, which determines the Meyer property on the substitution tilings from the expansion maps. [ABSTRACT FROM AUTHOR]

We describe computer algorithms that produce the complete set of isohedral tilings by n-omino or n-iamond tiles in which the tiles are fundamental domains and the tilings have pmm, pmg, pgg or cmm symmetry [1]. These symmetry groups are members of the crystal class D2 among the 17 two-dimensional symmetry groups [2]. We display the algorithms' output and give enumeration tables for small values of n. This work is a continuation of our earlier works for the symmetry groups p3, p31m, p3m1, p4, p4g, p4m, p6, and p6m [3-5]. [ABSTRACT FROM AUTHOR]

The article presents the computation for the perfect rhythmic tilings. It mentions that the perfect rhythmic tiling is computed by a computer program. It offers that references to similar work done by researchers Tom Johnson, C. J. Bouwkamp and N. J. A. Sloane. It adds that classical rhythmic canon survey and algorithms.

We describe computer algorithms that produce the complete set of isohedral tilings by n-omino or n-iamond tiles in which the tiles are fundamental domains and the tilings have pmm, pmg, pgg or cmm symmetry [1]. These symmetry groups are members of the crystal class D2 among the 17 two-dimensional symmetry groups [2]. We display the algorithms' output and give enumeration tables for small values of n. This work is a continuation of our earlier works for the symmetry groups p3, p31m, p3m1, p4, p4g, p4m, p6, and p6m [3-5]. [ABSTRACT FROM AUTHOR]

Abstract: Overlap coincidence in a self-affine tiling in is equivalent to pure point dynamical spectrum of the tiling dynamical system. We interpret the overlap coincidence in the setting of substitution Delone set in and find an efficient algorithm to check the pure point dynamical spectrum. This algorithm is easy to implement into a computer program. We give the program and apply it to several examples. In the course of the proof of the algorithm, we show a variant of the conjecture of Urbański (Solomyak (2006) ) on the Hausdorff dimension of the boundaries of fractal tiles. [ABSTRACT FROM AUTHOR]

In this paper we show that membership in finitely generated submonoids is undecidable for the free metabelian group of rank 2 and for the wreath product ℤ ≀(ℤ×ℤ). We also show that subsemimodule membership is undecidable for finite rank free (ℤ×ℤ)-modules. The proof involves an encoding of Turing machines via tilings. We also show that rational subset membership is undecidable for two-dimensional lamplighter groups. [ABSTRACT FROM AUTHOR]

Algorithmic self-assembly of D A tiles is known as a way to create nano∼cale structures with various patterns through a bottom-up approach. Several motifs for the tile system have been realized so far, although there are some limitations in design. Here we introduce a new tile system based on a DNA motif called 'T-motif', which complies with several design requirements for DNA algorithmic self-assembly. The tile system based on the T-motif has several characteristics arising from a structural difference with other existing motifs. Discussed are details of the structure, a design of tile sets, and some experimental results of algorithmic selfassembly as a demonstration to show the possibility for an implementation of one-dimensional cellular automata using this motif. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes directional Hartley transform (DirHT) in the Hartley domain by partitioning the two dimensional Hartley plane. Two different approaches, wrapping based directional Hartley transform (WDirHT) and overlapping based directional Hartley transform (ODirHT) have been proposed. WDirHT uses the Fourier integral operator (FIO) tiling scheme and ODirHT uses the ridgelet tiling scheme. WDirHT takes less computation time as compared to ODirHT, however, ODirHT has less redundancy factor as compared to WDirHT. The computational complexity of both WDirHT and ODirHT is for image. The two dimensional Hartley plane is neither symmetric nor antisymmetric, hence, each Hartley directional subband coefficient in the two dimensional Hartley plane is unique. As a result, features obtained from the Hartley domain are unique. These features are exploited for content based image retrieval (CBIR) application. The proposed CBIR algorithm using WDirHT and ODirHT is applied on AT&T face and Brodatz textures databases. Results show that retrieval rate of both WDirHT and ODirHT is better as compared to several other methods. Among WDirHT and ODirHT, WDirHT gives better retrieval rate. [Copyright &y& Elsevier]

We contribute to combinatorics and algorithmics of words by introducing new types of periodicities in words. A tiling period of a word w is partial word u such that w can be decomposed into several disjoint parallel copies of u, e.g. a ◊ b is a tiling period of aabb. We investigate properties of tiling periodicities and design an algorithm working in O(n log(n) log log(n)) time which finds a tiling period of minimal size, the number of such minimal periods and their compact representation. The combinatorics of tiling periods differs significantly from that for classical full periods, for example unlike the classical case the same word can have many different primitive tiling periods. We consider also a related new type of periods called in the paper multi-periods. As a side product of the paper we solve an open problem posted by T. Harju (2003). [ABSTRACT FROM AUTHOR]

In this paper, we introduce an analytical approach for the frequency warping transform. Criteria for the design of operators based on arbitrary warping maps are provided and an algorithm carrying out a fast computation is defined. Such operators can be used to shape the tiling of time-frequency (TF) plane in a flexible way. Moreover, they are designed to be inverted by the application of their adjoint operator. According to the proposed model, the frequency warping transform is computed by considering two additive operators: the first one represents its nonuniform Fourier transform approximation and the second one suppresses aliasing. The first operator is fast computable by various interpolation approaches. A factorization of the second operator is found for arbitrary shaped nonsmooth warping maps. By properly truncating the operators involved in the factorization, the computation turns out to be fast without compromising accuracy. [ABSTRACT FROM AUTHOR]

Intensive research on fractals began around 1980 and many new discoveries have been made. However, the connection between fractals, tilings and reptiles has not been thoroughly explored. This paper shows that a method, similar to that used to construct irregular tilings in ℜ2 can be employed to construct fractal tilings. Five main methods, including methods in Escher style paintings and the Conway criterion are used to create the fractal tilings. Also an algorithm is presented to generate fractal reptiles. These methods provide a more geometric way to understand fractal tilings and fractal reptiles and complements iteration methods. [ABSTRACT FROM AUTHOR]

Abstract: This paper extends, in a multi-dimensional framework, pattern recognition techniques for generation or recognition of digital lines. More precisely, we show how the connection between chain codes of digital lines and continued fractions can be generalized by a connection between tilings and multi-dimensional continued fractions. This leads to a new approach for generating and recognizing digital hyperplanes. [Copyright &y& Elsevier]

Abstract: Tiling systems are a well accepted model to define recognizable two-dimensional languages but they are not an effective device for recognition unless a scanning strategy for the pictures is fixed. We define a tiling automaton as a tiling system equipped with a scanning strategy and a suitable data structure. The class of languages accepted by tiling automata coincides with the REC family. In this framework it is possible to define determinism, non-determinism and unambiguity. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for two-dimensional languages. [Copyright &y& Elsevier]

In this paper, we study algorithms for tiling problems. We show that the conditions (T1) and (T2) of Coven and Meyerowitz [E. Coven and A. Meyerowitz, Tiling the integers with translates of one finite set, J. Algebra 212(1) (1999), pp. 161-174], conjectured to be necessary and sufficient for a finite set A to tile the integers, can be checked in time polynomial in diam (A). We also give heuristic algorithms to find all non-periodic tilings of a cyclic group N. In particular, we carry out a full classification of all non-periodic tilings of 144. [ABSTRACT FROM AUTHOR]

The musical notion of rhythmic canons has proved to be relevant to some non-trivial mathematical problems. After a survey of the main concepts of tiling rhythmic canons, we discuss recent developments that enable to make, or expect, definite progress on several open mathematical conjectures. [ABSTRACT FROM AUTHOR]

In the context of a syntactic approach to pattern recognition, there have been several studies in the last few decades ontheoretical models for generating or recognizing two-dimensional objects, pictures, and picture languages. Motivated by these studies, we have introduced a new notion of recognizability for a class of picture languages called iso-picture languages through iso-triangular tiling systems (ITS) and studied the properties of these languages [Kalyani et al.,2004]. In [Kalyani et al.,2005], we introduced iso-triangular domino systems (IDS) to recognize iso-picture languages, and proved the equivalence of ITS and IDS. In [Kalyani et al.,2006], we have constructed a two-dimensional online tessellation automaton (IPOTA) to recognize an iso-picture language and presented an algorithm to learn recognizable iso-picture languages from positive data and restricted subset queries. In this article, we introduce iso-triangular Wang systems (IWS) to recognize iso-picture languages. We prove that the family of iso-picture languages recognized by iso-triangular Wang systems ℒ(IWS) coincides with the family of iso-picture languages recognized by iso-triangular tiling systems ℒ(ITS). We show that ℒ(ITS) = ℒ(IDS) as a corollary and obtain that the families of iso-picture languages ℒ(ITS), ℒ(IDS), ℒ(IWS), and ℒ(IPOTA) all coincide. © 2009 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 19, 140–145, 2009. [ABSTRACT FROM AUTHOR]

Abstract: Tilings of the discrete plane generated by quasi-linear transformations (QLT) have been introduced by Nehlig [P. Nehlig, Applications quasi-affines: Pavages par images réciproques, Theoretical Computer Science 156 (1995) 1–38]. We studied these tilings and gave some results, such as periodicity and the number of neighbours of each of them [M.-A. Jacob-Da Col, Applications quasi-affines et pavages du plan discret, Theoretical Computer Science 259 (2001) 245–269. Also available in English: http://dpt-info.u-strasbg.fr/~jacob/articles/paving.pdf]. The aim of this paper is to go on with this study in the discrete -dimensional space ; we give a lower and an upper bound to the number of distinct tiles. We also give an algorithm to determine the points of a given tile, this algorithm will induce another algorithm to determine the number of distinct tiles associated to a QLT. [Copyright &y& Elsevier]

Abstract: On square or hexagonal lattices, tiles or polyominoes are coded by words. The polyominoes that tile the plane by translation are characterized by the Beauquier-Nivat condition. By using the constant time algorithms for computing the longest common extensions in two words, we provide a linear time algorithm in the case of pseudo-square polyominoes, improving the previous quadratic algorithm of Gambini and Vuillon. We also have a linear algorithm for pseudo-hexagon polyominoes not containing arbitrarily large square factors. The results are extended to more general tiles. [Copyright &y& Elsevier]

Stencil computations constitute the kernel of many scientific applications. Tiling is often used to improve the performance of stencil codes for data locality and parallelism. However, tiled stencil codes typically require shadow regions, whose management becomes a burden to programmers. In fact, it is often the case that the code required to manage these regions, and in particular their updates, is much longer than the computational kernel of the stencil. As a result, shadow regions usually impact programmers' productivity negatively. In this paper, we describe overlapped tiling, a construct that supports shadow regions in a convenient, flexible and efficient manner in the context of the hierarchically tiled array (HTA) data type. The HTA is a class designed to express algorithms with a high degree of parallelism and/or locality as naturally as possible in terms of tiles. We discuss the syntax and implementation of overlapped HTAs as well as our experience in rewriting parallel and sequential codes using them. The results have been satisfactory in terms of both productivity and performance. For example, overlapped HTAs reduced the number of communication statements in non-trivial codes by 78% on average while speeding them up. We also examine different implementation options and compare overlapped HTAs with previous approaches. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

A method is proposed for constructing angular values for Delone sets, which can be used as a basis to classify voids in crystal structures. An algorithm for determining the crystalline module in a crystal structure from the generalized void, including nonequivalent empty spheres of the corresponding symplectic Delone tiling, is considered (computer simulation). [ABSTRACT FROM AUTHOR]

Tiling DNA microarrays extend current microarray technology by probing the non-repeat portion of a genome at regular intervals in an unbiased fashion. A fundamental problem in the analysis of these data is the detection of genomic regions that are differentially transcribed across multiple conditions. We propose a linear time algorithm based on segmentation techniques and linear modeling that can work at a user-selected false discovery rate (FDR). It also attains a fourfold sensitivity gain over the only competing algorithm when applied to a whole genome transcription data set spanning the embryonic development of Drosophila melanogaster. [ABSTRACT FROM AUTHOR]

We present a general framework for the modeling and optimization of scalable multi-projector displays. Based on this framework, we derive algorithms that can robustly optimize the visual quality of an arbitrary combination of projectors without manual adjustment. When the projectors are tiled, we show that our framework automatically produces blending maps that outperform state-of-the-art projector blending methods. When all the projectors are superimposed, the framework can produce high-resolution images beyond the Nyquist resolution limits of component projectors. When a combination of tiled and superimposed projectors are deployed, the same framework harnesses the best features of both tiled and superimposed multi-projector projection paradigms. The framework creates for the first time a new unified paradigm that is agnostic to a particular configuration of projectors yet robustly optimizes for the brightness, contrast, and resolution of that configuration. In addition, we demonstrate that our algorithms support high resolution video at real-time interactive frame rates achieved on commodity graphics platforms. This work allows for inexpensive, compelling, flexible, and robust large scale visualization systems to be built and deployed very efficiently. [ABSTRACT FROM AUTHOR]

Modelling of the growth of a decagonal Cartwheel-type tiling is not described well enough by the well known matching rules of Penrose tiles. This paper presents a deterministic algorithm which allows the calculation of a perfect Cartwheel-type tiling by the successive transfer of recursive values out of each cluster cell, Q, to its neighbour cells. [ABSTRACT FROM AUTHOR]

We show a simple method to generate polyominoes and polyiamonds that produce isohedral tilings with p3, p4 or p6 rotational symmetry by using n line segments between lattice points on a regular hexagonal, square and triangular lattice, respectively. We exhibit all possible tiles generated by this algorithm up to n = 9 for p3, n = 8 for p4, and n = 13 for p6. In particular, we determine for n ≤ 8 all n-ominoes that are fundamental domains for p4 isohedral tilings. [ABSTRACT FROM AUTHOR]

Adaptive multiscale representations via quadtree splitting and two-dimensional (2-D) wavelet packets, which amount to space and frequency decompositions, respectively, are powerful concepts that have been widely used in applications. These schemes are direct extensions of their one-dimensional counterparts, in particular, by coupling of the two dimensions and restricting to only one possible further partition of each block into four subblocks. In this paper, we consider more flexible schemes that exploit more variations of multidimensional data structure. In the mean- time, we restrict to tree-based decompositions that are amenable to fast algorithms and have low indexing cost. Examples of these decomposition schemes are anisotropic wavelet packets, dyadic rectangular tilings, separate dimension decompositions, and general rectangular tilings. We compute the numbers of possible decompositions for each of these schemes. We also give bounds for some of these numbers. These results show that the new rectangular tiling schemes lead to much larger sets of 2-D space and frequency decompositions than the commonly-used quadtree-based schemes, therefore bearing the potential to obtain better representation for a given image. [ABSTRACT FROM AUTHOR]

We are concerned with the tiling flow T associated to a substitution 4 over a finite alphabet. Our focus is on substitutions that are unimodular Pisot, i.e., their matrix is unimodular and has all eigenvalues strictly inside the unit circle with the exception of the Perron eigenvalue λ > 1. The motivation is provided by the (still open) conjecture asserting that T has pure discrete spectrum for any such 4. We develop a number of necessary and sufficient conditions for pure discrete spectrum, including: injectivity of the canonical torus map (the geometric realization), Geometric Coincidence Condition, (partial) commutation of T and the dual Rd-1-action measure and tiling properties of Rauzy fractals, and concrete algorithms. Some of these are original and some have already appeared in the literature—as sufficient conditions only—but they all emerge from a unified approach based on the new device: the strand space Fϕ of ϕ. The proof of the necessity hinges on determination of the discrete spectrum of T as that of the associated Kronecker toral flow. [ABSTRACT FROM AUTHOR]

Abstract: We produce an algorithm that is optimal with respect to both space and execution time to generate all the lozenge (or domino) tilings of a hole-free, general-shape domain given as input. We first recall some useful results, namely the distributive lattice structure of the space of tilings and Thurston''s algorithm for constructing a particular tiling. We then describe our algorithm and study its complexity. [Copyright &y& Elsevier]

An algorithm for the growth of two-dimensional Penrose tiling, based on symmetry operations on a seed rhombus, is discussed and demonstrated. Independent of empirical matching rules, as suggested by Penrose [Bull. Inst. Math. Appl. 10 266 (1974)], and also overcoming the scaling-down operation, as proposed by Ramachandrarao et al . (Acta Crystallogr. A 47 210 (1991)], the present algorithm follows a mechanism akin to self-assembly and can be continued ad infinitum . [ABSTRACT FROM AUTHOR]