Thurston Algorithm And Evolutionary Strategy One For Circle Packings

A circle packing is a configuration of circles in a constant curvaturesurface with prescribed pattern of tangencies. In 1985 W. P. Thurstonconjectured that the Riemann mapping function f from a simply con-nected regionΩonto the unit disk D can be approximated using hexago-nal circle packings. In 1987 this conjecture was proved by B. Rodin andD. Sullivan, which gives a new discrete geometry view of the Riemannmapping. After then, much research on circle packings and their relativeapplications followed. For the study of circle configurations, classical cir-cle packings consisting of disjoint open disks were generalized to circlepatterns, where the disks may overlap. In this thesis, our main work isas follows. First, we use Thurston'idea to investigate circle pattern al-gorithms. Given a weighted triangulation of a closed topological disk, weuse Thurston'iterative approach, combining with the Uniform NeighborModel (UNM), to describe an algorithm which solves the radii of circlepattern realizing the weighted triangulation. This extends Thurston'al-gorithm of circle packings to the case of circle patterns. Secondly, weapply evolution strategy idea to study circle packing algorithms. Givena triangulation of a closed topological disk, we reduce the problem offinding the radii of circle packing for the triangulation to the one of evo-lution strategy. Next, we use techniques of improved evolution strategyto describe an algorithm which solves the radii of circle packing for thetriangulation. It can be seen from simulate problems that the evolu-tionary algorithm is e?cient and feasible in finding the radii of circle packings, which provides another circle packing algorithm.