This thesis is a study of circle packings for arbitrary combinatorial tori in the geometric setting of affine tori. Certain new tools needed for this study, such as face labels instead of the usual vertex labels, are described. It is shown that to each combinatorial torus there corresponds a two real parameter family of affine packing labels. A construction of circle packings for combinatorial fundamental domains from affine packing labels is given. It is demonstrated that such circle packings have two affine side-pairing maps, and also that these side-pairing maps depend continuously on the two real parameters.

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

AN ABSTRACT OF THE DISSERTATION OFDinush Lanka Panditharathna Jayasooriya Arachchilage, forthe Doctor of Philosophy degree in MATHEMATICS, presented on June 22, 2020 at SouthernIllinois University Carbondale.TITLE: SPIN NETWORK EVALUATION AND THE ASYMPTOTIC BEHAVIORMAJOR PROFESSOR: Dr. Jerzy KocikGraphically, a spin network is a trivalent graph with weights on each edge. At anyof the vertices, the sum of all three weights is even and the sum of any two weights isgreater than or equal to the remaining weight. If the spin network has no free ends, thenwe can evaluate the spin network. Here, we propose a method to evaluate some basic spinnetworks using the idea of Stirling triangle.Tangent circles with integer curvatures are a natural source to make a spin network.In particular, there are spin networks corresponding the Apollonian circle packing and theFord circle packing. We obtain the recurrence relations using the Descartes circle theoremand we evaluate the Apollonian spin network and the Ford circle spin network. We alsodiscuss the asymptotic behavior of the Ford circle spin network.

Thesis (Ph. D.)--Florida State University, 2006. / Advisor: Philip Bowers, Florida State University, College of Arts and Sciences, Dept. of Mathematics. Title and description from dissertation home page (viewed Sept. 15, 2006). Document formatted into pages; contains ix, 98 pages. Includes bibliographical references.

Cable harness is an integral part of a modern-day automobile. The design of many mechanical components is based on the cable harness and hence it is important to accurately calculate the space occupied by cable harness. In this thesis, a theoretical model representing n arbitrarily sized cables was used to generate a packing of the cable harness, and the space occupied by them was calculated. The model was used to develop an algorithm that generated a feasible configuration and a container around that packing. The optimisation toolbox in MATLAB was also used to calculate the space and optimise the container size. A customised standalone tool was developed in MATLAB by utilising the established methods, that enables calculation of space occupied by cables at various points of interest along the truck chassis for Scania CV.

Geometric Circle Packings are of interest not only for their aesthetic appeal but also their relation to discrete analytic function theory. This thesis presents new computational methods which enable additional practical applications for circle packing geometry along with providing a new discrete analytic interpretation of the classical Schwarzian derivative and traditional univalence criterion of classical analytic function theory. To this end I present a new method of computing the maximal packing and solving the circle packing layout problem for a simplicial 2-complex along with additional geometric variants and applications. This thesis also presents a geometric discrete Schwarzian quantity whose value is associated with the classical Schwarzian derivative. Following Hille, I present a characterization of circle packings as the ratio of two linearly independent solutions of a discrete difference equation taking the discrete Schwarzian as a parameter. This characterization then gives a discrete interpretation of the classical univalence criterion of Nehari in the circle packing setting.

The two-dimension packing problem is concerned with the arrangement of items without overlaps inside a container. In particular we have considered the case when the items are circular objects, some of the general examples that can be found in the industry are related with packing, storing and transportation of circular objects. Although there are several approaches we want to investigate the use of formulation space search. Formulation space search is a fairly recent method that provides an easy way to escape from local optima for non-linear problems allowing to achieve better results. Despite the fact that it has been implemented to solve the packing problem with identical circles, we present an improved implementation of the formulation space search that gives better results for the case of identical and non-identical circles, also considering that they are packed inside different shaped containers, for which we provide the needed modifications for an appropriate implementation. The containers considered are: the unit circle, the unit square, two rectangles with different dimension (length 5, width 1 and length 10 width 1), a right-isosceles triangle, a semicircle and a right-circular quadrant. Results from the tests conducted shown several improvements over the best previously known for the case of identical circles inside three different containers: a right-isosceles triangle, a semicircle and a circular quadrant. In order to extend the scope of the formulation space search approach we used it to solve mixed-integer non-linear problems, in particular those with zero-one variables. Our findings suggest that our implementation provides a competitive way to solve these kind of problems.

In the real world, many problems are continuous in nature. In some cases, finding the global solutions for these problems is di±cult. The reason is that the problem's objective function is non convex, nor concave and even not differentiable. Tackling these problems is often computationally too expensive. Although the development in computer technologies are increasing the speed of computations, this often is not adequate, particularly if the size of the problem's instance are large. Applying exact methods on some problems may necessitate their linearisation. Several new ideas using heuristic approaches have been considered particularly since they tackle the problems within reasonable computational time and give an approximate solution. In this thesis, the variable neighbourhood search (VNS) metaheuristic (the framework for building heuristic) has been considered. Two variants of variable neighbourhood search metaheuristic have been developed, continuous variable neighbourhood search and reformulation descent variable neighbourhood search. The GLOB-VNS software (Drazic et al., 2006) hybridises the Microsoft Visual Studio C++ solver with variable neighbourhood search metaheuristics. It has been used as a starting point for this research and then adapted and modified for problems studied in this thesis. In fact, two problems have been considered, censored quantile regression and the circle packing problem. The results of this approach for censored quantile regression outperforms other methods described in the literature, and the near-optimal solutions are obtained in short running computational time. In addition, the reformulation descent variable neighbourhood search variant in solving circle packing problems is developed and the computational results are provided.

Dans ce travail, nous nous sommes intéressés à l'étude asymptotique d'objets combinatoires aléatoires. Deux thèmes ont particulièrement retenu notre attention : les cartes planaires aléatoires et les modèles combinatoires liés à la théorie des fragmentations. La théorie mathématique des cartes planaires aléatoires est née à l'aube de notre millénaire avec les travaux pionniers de Benjamini & Schramm, Angel & Schramm et Chassaing & Schaeffer. Elle a ensuite beaucoup progressé, mais à l'heure où ces lignes sont écrites, de nombreux problèmes fondamentaux restent ouverts. Résumons en quelques mots clés nos principales contributions dans le domaine : l'introduction et l'étude du cactus brownien (avec J.F. Le Gall et G. Miermont), l'étude de la quadrangulation infinie uniforme vue de l'infini (avec L. Ménard et G. Miermont), ainsi que des travaux plus théoriques sur les graphes aléatoires stationnaires d'une part et les graphes empilables dans $\R^d$ d'autre part (avec I. Benjamini). La théorie des fragmentations est beaucoup plus ancienne et remonte à des travaux de Kolmogorov (1941) et de Filippov (1961). Elle est maintenant bien développée (voir par exemple l'excellent livre de J. Bertoin), et nous ne nous sommes pas focalisés sur cette théorie mais plutôt sur ses applications à des modèles combinatoires. Elle s'avère en effet très utile pour étudier différents modèles de triangulations récursives du disque (travail effectué avec J.F. Le Gall) et les recherches partielles dans les quadtrees (travail effectué avec A. Joseph). / The subject of this thesis is the asymptotic study of large random combinatorial objects. This is obviously very broad, and we focused particularly on two themes: random planar maps and their limits, and combinatorial models that are in a way linked to fragmentation theory. The mathematical theory of random planar maps is quite young and was triggered by works of Benjamini & Schramm, Angel & Schramm and Chassaing & Schaeffer. This fascinating field is still growing and fundamental problems remain unsolved. We present some new results in both the scaling limit and local limit theories by introducing and studying the Brownian Cactus (with J.F. Le Gall and G. Miermont), giving a new view point, a view from infinity, at the Uniform Infinite Planar Quadrangulation (UIPQ) and bringing more theoretical contributions on stationary random graphs and sphere packable graphs (with I. Benjamini). Fragmentation theory is much older and can be tracked back to Kolmogorov and Filippov. Our goal was not to give a new abstract contribution to this well-developed theory (see the beautiful book of J. Bertoin) but rather to apply it to random combinatorial objects. Indeed, fragmentation theory turned out to be useful in the study of the so-called random recursive triangulations of the disk (joint work with J.F. Le Gall) and partial match queries in random quadtrees (joint work with A. Joseph).

Verallgemeinerungen bekannter Existenz- und Eindeutigkeitsaussagen für gebietsfüllende Kreispackungen. Für jedes beschränkte, einfach zusammenhängende Gebiet und für jeden zulässigen Komplex existiert eine gebietsfüllende, verallgemeinerte Kreispackung, die einer beliebigen der folgenden Normalisierungen genügt. alpha-beta-gamma: drei Randkreise sind je einem Randpunkt (Primende) zugeordnet alpha-gamma: ein Kreis mit fixem Mittelpunkt und ein Randkreis mit zugeordnetem Primende alpha-beta: zwei Kreise mit fixen Mittelpunkten Bedingungen werden angegeben, unter welchen die aufgeführten Normalisierungen eindeutige Lösungen implizieren, welche zudem stetig von den Normalisierungsparametern abhängen. Ist der Alpha-Kreis ein innerer Kreis, dann wird gezeigt, dass die alpha-beta Normalisierung im Allg. keine Eindeutigkeit liefert. Bedingungen werden aufgeführt, die nicht-entartete Lösungen (klassische Kreispackungen) garantieren. Alle Beweise sind möglichst elementar und unabhängig von existierenden Kreispackungs-Ergebnissen. / Existing existence and uniqueness results in the field of domain filling circle packings are generalized. For every bounded, simply connected domain, for every admissible complex, and under any of the following normalizations it is shown that there is a domain filling generalized circle packing. alpha-beta-gamma: three boundary disks are each associated with a boundary point (prime end) alpha-gamma: one disk with fixed center and one boundary disk with associated prime end alpha-beta: two disks with fixed centers Conditions are given under which the stated normalizations yield unique solutions, which then depend continuous on some normalization parameters. For the special case of an interior alpha disk it is shown that the alpha-beta normalization does not yield uniqueness in general. Several conditions are stated that guarantee non-degenerate solutions (classical circle packings). All proofs are kept as elementary as possible and independent of existing circle packing results.