Minimum Cost Polygon Overlay (MCPO) is a unique two-dimensional optimization problem that involves the task of covering a polygon shaped area with a series of rectangular shaped panels. The challenges in solving MCPO problems are related to the interdependencies that exist among the parameters and constraints that may be applied to the solution.This thesis examines the MCPO problem to construct a model that captures essential parameters to be solved using optimization algorithms. The purpose of the model is to make it possible that a solution for an MCPO problem can be generated automatically. A software application has been developed to provide a framework for validating the model.The development of the software has uncovered a host of geometric operations that are required to enable optimization to take place. Many of these operations are non-trivial, demanding novel, well-constructed algorithms based on careful appreciation of the nature of the problem.For the actual optimization task, three algorithms have been implemented: a greedy search, a Monte Carlo method, and a Genetic Algorithm. The behavior of the completed software is observed through its application on a series of test data. The results are presented to show the effectiveness of the software under various settings. This is followed by critical analysis of various findings of the research.Conclusions are drawn to summarize lessons learned from the research. Important issues about which no satisfactory explanation exists are given as material to be studied by future research.

Typescript. Includes bibliographical references.

La modélisation numérique des écoulements de glace est indispensable pour prédire l’évolution des calottes polaires suite au réchauffement climatique. De récentes études ont souligné l’importance des modèles d’écoulement dits d’ordre supérieur voir même de Stokes au lieu de la traditionnelle approximation de couche mince dont les hypothèses ne sont pas valables dans certaines zones critiques mais à l’étendue limitée. Cependant, ces modèles d’ordre supérieur sont difficiles à utiliser à l’échelle d’un continent en raison de leurs temps de calculs prohibitifs. Ce travail de thèse propose une nouvelle technique qui permet de réduire les temps de calculs tout en maximisant la précision des modèles. Plusieurs modèles d’écoulement de glace de complexité variables ont été mis en place dans ISSM (Ice Sheet System Model), un code élément fini massivement parallèle développé par le Jet Propulsion Laboratory. L’analyse et la comparaison des différents modèles, à la fois sur des cas théoriques et réels, montrent que l’utilisation des modéles les plus complets est principalement nécessaire au voisinage de la zone d’échouage, transition entre les parties flottantes et posées de la glace, mais aussi que des modèles plus simples peuvent être utilisés sur la majeure partie des glaciers. Coupler différents modèles présente donc un avantage significatif en terme de temps de calcul mais aussi d’amélioration de la physique utilisées dans les modèles. Plusieurs méthodes de couplage de modèles existent et sont présentées dans ce manuscrit. Une nouvelle technique, dite de tuilage, particulièrement adaptée au couplage de modèles d’écoulement de glace est décrite ici : son principe repose sur la superposition et le raccordement de plusieurs modèles mécaniques. Une analyse mathématique est effectuée afin de définir les conditions d’utilisation de cette méthode de tuilage. Le traitement du couplage entre un modèle de Stokes et des modèles simplifiés, pour lesquels le calcul des vitesses horizontales et verticales est découplé, est ensuite présenté. Cette technique a été mise en place dans ISSM afin de pouvoir créer des modèles hybrides combinant plusieurs modèles d’écoulement de complexité variable. Après avoir été validée sur des cas synthétiques, cette technique est utilisée sur des glaciers réels comme Pine Island Glacier, dans l’Antarctique de l’Ouest, afin d’illustrer sa pertinence. Les modèles hybrides ont le potentiel d’améliorer la précision des résultats en combinant différents modèles mécaniques, utilisés chacun dans les zones où leurs approximations sont valides, tout en réduisant les temps de calcul et en étant compatibles avec les ressources informatiques actuelles. / Ice flow numerical models are essential for predicting the evolution of ice sheets in a warming climate. Recent research emphasizes the need for higher-order and even full-Stokes flow models instead of the traditional Shallow-Ice Approximation whose assumptions are not valid in certain critical but spatially limited areas. These higher-order models are however computationally intensive and difficult to use at the continental scale. The purpose of this work, therefore, is to develop a new technique that reduces the computational cost of ice flow models while maximizing their accuracy. To this end, several ice flow models of varying order of complexity have been implemented in the Ice Sheet System Model, a massively parallelized finite element software developed at the Jet Propulsion Laboratory. Analysis and comparison of model results on both synthetic and real geometries shows that sophisticated models are only needed in the grounding line area, transition between grounded and floating ice, whereas simpler models yield accurate results in most of the model domain. There is therefore a strong need for coupling such models in order to balance computational cost and physical accuracy. Several techniques and frameworks dedicated to model coupling already exist and are investigated. A new technique adapted to the specificities of ice flow models is developed: the Tiling method, a multi-model computation strategy based on the superposition and linking of different numerical models. A mathematical analysis of a mixed Tiling formulation is first performed to define the conditions of application. The treatment of the junction between full-Stokes and simpler models that decouple horizontal and vertical equation is then elaborated in order to rigorously combine all velocity components. This method is finally implemented in the Ice Sheet System Model to design hybrid models that combine several ice flow approximations of varying order of complexity. Following a validation on synthetic geometries, this method is applied to real cases, such as Pine Island Glacier, in West Antarctica, to illustrate its relevance. Hybrid models have the potential to significantly improve physical accuracy by combining models in their domain of validity, while preserving the computational cost and being compatible with the actual computational resources.

No description available.

Ce mémoire de thèse est une contribution à l'étude des canons modulo p. De nombreux outils mathématiques et informatiques ont été employés pour l'étude des canons rythmiques mosaïques. La recherche récente s'est particulièrement attachée à trouver les canons sans périodicité interne, dits de Vuza. Ces canons ont la particularité d'être une base pour la construction de tous les canons rythmiques mosaïques, cependant ils sont très difficiles à obtenir. La meilleure méthode actuellement est un algorithme exhaustif de recherche, qui malgré de récentes améliorations reste exponentiel. Plusieurs techniques ont été utilisées dans l'espoir de mieux les comprendre ou de les générer plus rapidement. Ce mémoire présente donc un nouveau sujet d'étude pour mieux comprendre le pavage apériodique. / This thesis is a contribution to the study of modulo p tiling. Many mathematical and computational tools were used for the study of rhythmic tiling canons. Recent research has mainly focused in finding tiling without inner periodicity, being called Vuza canons. Those canons are a constructive basis for all rhythmic tiling canons, however, they are really difficult to obtain. Best current method is a brut force exploration that, despite a few recent enhancements, is exponential. Many technics have been used, hoping to understand Vuza canons better or to generate them faster. Hence, this thesis presents a completely new way to study aperiodic tiling.

<p>A topologically interlocked material (TIM) system belongs to a class of architectured materials and is known to perform outstanding mechanical properties such as stiffness, strength, and toughness. TIM systems are assemblies of polyhedral or building blocks, where individual elements constrain each other on inclined sides of building blocks. This thesis first focuses on developing novel designs of TIM plates composed of building blocks that interact with each other. The resulting TIM systems can be characterized concerning their periodicity and symmetry. Consequently, this study investigates how the proposed geometric features enhance mechanical properties and contribute to emerging properties. Specifically, four research questions provide a clear direction and framework for the investigation. For efficient analysis, finite element calculations are employed, and physical validation methods are used to verify them.</p> <p>The first research question is how the mechanical properties of aperiodic systems differ from those of periodic systems. Aperiodic systems offer diverse possibilities in terms of forms and arrangements. In this thesis, aperiodicity is further divided into two aspects: disrupting symmetry and preserving symmetry. In the approach that disrupts symmetry, the shapes of the tiles are randomly generated. An aperiodic system does not necessarily possess inherently superior or inferior mechanical properties compared to a periodic system. However, the flexibility of aperiodic systems allows for numerous forms and arrangements, presenting promising alternatives to identify factors or patterns that contribute to improved mechanical performance. To simplify these complex configurations, network theory is employed.</p> <p>Each building and its contact interfaces are represented as nodes and links. By utilizing network theory, a focused analysis of the links is conducted, enabling a comprehensive understanding of force propagation across TIM systems. The quantification of the significance of each link assists in reinforcing critical links while potentially sacrificing less critical ones.</p> <p>This approach not only simplifies the research problem but also facilitates the creation of customized design systems by adjusting the links.</p> <p>The other approach to achieve aperiodicity while preserving symmetry utilizes quasicrystal structures. This is based on another research question: What are the benefits of creating TIM systems with quasi-crystal tilting? Quasi-crystals possess a unique characteristic of maintaining 5-fold rotational symmetry while breaking away from periodic patterns observed in traditional systems. The arrangement of elements in quasi-crystal structures extends in a non-repetitive pattern from the center outward, offering a multitude of potential possibilities for TIM systems. By incorporating quasi-crystal tiling, TIM systems are expected to open up exceptional mechanical properties and unconventional behaviors.</p> <p>The third research question investigates whether the influence on mechanical performance varies based on the symmetry level of TIM systems. Despite using identical unit blocks, the arrangement of an assembly can lead to different levels of symmetry. Furthermore, it is possible to modify the symmetry of the unit block, thereby impacting the overall symmetry of the assembly. To achieve this, the symmetry of a unit block is adjusted by modifying the angles of side faces, transitioning from larger angles to smaller angles or vice versa. This modification introduces directionality (rotational symmetry) to the unit block and creates a greater variety of symmetry levels depending on the arrangements of these blocks. By implementing a broader range of symmetry levels that conventional TIM systems cannot achieve, this research aims to investigate the relationship between these symmetries and mechanical properties.</p> <p>The fourth research question is about what emerging properties could be present in TIM systems. While the primary application of TIMs is to enhance the damage tolerance of brittle materials against an external load, there have been ongoing attempts to research emerging properties like negative stiffness, sound absorption, and chirality. Chirality, in particular, serves as a valuable geometric property to describe a circulation of force propagation. Generally, the ability of TIM systems to carry transverse loads is explained through equivalent Mises truss along x− and y − axis. However, chirality enables the representation of not only axial force paths but also circulations of forces within TIM systems. In addition, a rich variety of geometric patches are observed in quasi-crystal structures. In crystal structures, a limited number of patches are repetitively arranged, resulting in a restricted range of properties. However, quasi-crystals like Penrose are non-periodic and possess a greater capacity to generate diverse patches, allowing for the selection of various mechanical properties.</p>

Nous avons étudié la dynamique de Glauber sur les pavages de domaines finies du plan par des losanges ou par des dominos de taille 2 × 1. Ces pavages sont naturellement associés à des surfaces de R^3, qui peuvent être vues comme des interfaces dans des modèles de physique statistique. En particulier les pavages par des losanges correspondent au modèle d'Ising tridimensionnel à température nulle. Plus précisément les pavages d'un domaine sont en bijection avec les configurations d'Ising vérifiant certaines conditions au bord (dépendant du domaine pavé). Ces conditions forcent la coexistence des phases + et - ainsi que la position du bord de l'interface. Dans la limite thermodynamique où L, la longueur caractéristique du système, tend vers l'infini, ces interfaces obéissent à une loi des grand nombre et convergent vers une forme limite déterministe ne dépendant que des conditions aux bord. Dans le cas où la forme limite est planaire et pour les losanges, Caputo, Martinelli et Toninelli [CMT12] ont montré que le temps de mélange Tmix de la dynamique est d'ordre O(L^{2+o(1)}) (scaling diffusif). Nous avons généralisé ce résultat aux pavages par des dominos, toujours dans le cas d'une forme limite planaire. Nous avons aussi prouvé une borne inférieure Tmix ≥ cL^2 qui améliore d'un facteur log le résultat de [CMT12]. Dans le cas où la forme limite n'est pas planaire, elle peut être analytique ou bien contenir des parties “gelées” où elle est en un sens dégénérée. Dans le cas où elle n'a pas de telle partie gelée, et pour les pavages par des losanges, nous avons montré que la dynamique de Glauber devient “macroscopiquement proche” de l'équilibre en un temps L^{2+o(1)} / We studied the Glauber dynamics on tilings of finite regions of the plane by lozenges or 2 × 1 dominoes. These tilings are naturally associated with surfaces of R^3, which can be seen as interfaces in statistical physics models. In particular, lozenge tilings correspond to three dimensional Ising model at zero temperature. More precisely, tilings of a finite regions are in bijection with Ising configurations with some boundary conditions (depending on the tiled domain). These boundary conditions impose the coexistence of the + and - phases, together with the position of the boundary of the interface. In the thermodynamic limit where L, the characteristic length of the system, tends toward infinity, these interface follow a law of large number and converge to a deterministic limit shape depending only on the boundary condition. When the limit shape is planar and for lozenge tilings, Caputo, Martinelli and Toninelli [CMT12] showed that the mixing time of the dynamics is of order (L^{2+o(1)}) (diffusive scaling). We generalized this result to domino tilings, always in the case of a planar limit shape. We also proved a lower bound Tmix ≥ cL^2 which improve on the result of [CMT12] by a log factor. When the limit shape is not planar, it can either be analytic or have some “frozen” domains where it is degenerated in a sense. When it does not have such frozen region, and for lozenge tilings, we showed that the Glauber dynamics becomes “macroscopically close” to equilibrium in a time L^{2+o(1)}

<p>Limit-periodic (LP) structures exhibit a type of nonperiodic order yet to be found in a natural material. A recent result in tiling theory, however, has shown that LP order can spontaneously emerge in a two-dimensional (2D) lattice model with nearest-and next-nearest-neighbor interactions. In this dissertation, we explore the question of what types of interactions can lead to a LP state and address the issue of whether the formation of a LP structure in experiments is possible. We study emergence of LP order in three-dimensional (3D) tiling models and bring the subject into the physical realm by investigating systems with realistic Hamiltonians and low energy LP states. Finally, we present studies of the vibrational modes of a simple LP ball and spring model whose results indicate that LP materials would exhibit novel physical properties.</p><p>A 2D lattice model defined on a triangular lattice with nearest- and next-nearest-neighbor interactions based on the Taylor-Socolar (TS) monotile is known to have a LP ground state. The system reaches that state during a slow quench through an infinite sequence of phase transitions. Surprisingly, even when the strength of the next-nearest-neighbor interactions is zero, in which case there is a large degenerate class of both crystalline and LP ground states, a slow quench yields the LP state. The first study in this dissertation introduces 3D models closely related to the 2D models that exhibit LP phases. The particular 3D models were designed such that next-nearest-neighbor interactions of the TS type are implemented using only nearest-neighbor interactions. For one of the 3D models, we show that the phase transitions are first order, with equilibrium structures that can be more complex than in the 2D case. </p><p>In the second study, we investigate systems with physical Hamiltonians based on one of the 2D tiling models with the goal of stimulating attempts to create a LP structure in experiments. We explore physically realizable particle designs while being mindful of particular features that may make the assembly of a LP structure in an experimental system difficult. Through Monte Carlo (MC) simulations, we have found that one particle design in particular is a promising template for a physical particle; a 2D system of identical disks with embedded dipoles is observed to undergo the series of phase transitions which leads to the LP state. </p><p>LP structures are well ordered but nonperiodic, and hence have nontrivial vibrational modes. In the third section of this dissertation, we study a ball and spring model with a LP pattern of spring stiffnesses and identify a set of extended modes with arbitrarily low participation ratios, a situation that appears to be unique to LP systems. The balls that oscillate with large amplitude in these modes live on periodic nets with arbitrarily large lattice constants. By studying periodic approximants to the LP structure, we present numerical evidence for the existence of such modes, and we give a heuristic explanation of their structure.</p> / Dissertation

In 1961, P. W. Kasteleyn provided a baffling-looking solution to an apparently simple tiling problem: how many ways are there to tile a rectangular region with dominos? We examine his proof, simplifying and clarifying it into this nearly self-contained work.

Denote by gdist(p) the least number of cells that have to be changed to get a latin square from the table of addition modulo prime p. A conjecture of Drápal, Cavenagh and Wanless states that there exists c > 0 such that gdist(p) ≤ c log(p). In this work we prove the conjecture for c ≈ 7.21, and the proof is done by constructing a dissection of an equilateral triangle of side n into O(log(n)) equilateral triangles. We also show a proof of the lower bound c log(p) ≤ gdist(p) with improved constant c ≈ 2.73. At the end of the work we present computational data which suggest that gdist(p)/ log(p) ≈ 3.56 for large values of p.