文档介绍：圆填充的Thurston与进化策略算法
摘要
圆填充是常曲率曲面上具有特定相切模式的一种圆格局。在1985年Fields奖
提出一个猜测:六边形圆填充可用来近似共形映射。1987年B.
Rodin 与D. Sullivan 方案的收敛性,这将圆填充与共形映
射建立了联系,给共形映射提供了一个崭新的离散几何观点。随后,出现大
量的关于圆填充及其应用的研究。对圆格局的研究,由其内部不相交的圆
组成的经典圆填充发展为其内部可以重叠的圆组成的圆填充,后者也收做
圆模式。本文的主要工作:第一,应用Thurston思想研究圆模式的算法。对
于给定一个闭拓扑圆盘的加权三角剖分,根据Thurston 的基本迭代法思想,
结合UNM模式,我们描述了实现这个加权三角剖分的圆模式的半径函数的
算法。这将圆填充的Thurston算法推广到圆模式的情形。第二,应用进化策
略思想研究圆填充的算法。对于给定一个闭拓扑圆盘的三角剖分,我们将
求解关于该三角剖分的圆填充的半径函数问题归结为进化策略问题,然后,
利用改进的进化策略思想,给出求解圆填充半径函数的算法。从仿真的例
子可以看出,圆填充的进化策略算法是行之有效的,这为求解圆填充的半
径函数提供了另一种算法。
关键词:圆填充圆模式单纯复形进化策略单基因突变
1
THURSTON ALGORITHM AND EVOLUTIONARY
STRATEGY ONE FOR CIRCLE PACKINGS
ABSTRACT
A circle packing is a configuration of circles in a constant curvature
surface with prescribed pattern of tangencies. In 1985 W. P. Thurston
conjectured 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 and
D. Sullivan, which gives a new discrete geometry view of the Riemann
mapping. After then, much research on circle packings and their relative
applications followed. For the study of circle configurations, classical cir-
cle packings consisting of disjoint open disks were generalized to circle
patterns, where the disks may overlap. In this thesis, our main work is
as follows. First, we use Thurston’ idea to investigate circle pattern al-
gorithms. Given a weighted triangulation of a closed topological disk, we
use Thurston’ iterative approach, combining with the Uniform Neighbor
Model (UNM), to describe an algorithm which solves the radii of circle
pattern realizing the weighted triangulation. This extends Thurston’ al-
gorithm of circle packings to the case of circle patterns. Secondly, we
apply evolution strategy idea to study circle packing algorithms. Given
a triangulation of a closed topological disk, we reduce the problem of
finding