共形结构比黎曼度量结构更灵活、比拓扑结构更具有刚性. 它能处理大量黎曼几何

共形结构比黎曼度量结构更灵活、比拓扑结构更具有刚性

. 它能处理大量黎曼几何

不能有效处理的变换
, 这些变换还能保持很多拓扑方法会丢失的几何信息.

计算共形几何

张威应用数学

11006059

1

引言

共形几何是纯数学中很多学科的交叉领域

, 比如黎曼曲面理论、微分几何、代数曲

线、代数拓扑、偏微分方程、复分析等等

. 它有很长的历史, 至今在现代几何与现代物理中

仍然非常活跃

. 比如超弦理论中的共形场和理论物理中的模空间理论都是当今快速发展

的研究领域

.

近些年来

, 随着三维数字扫描仪、计算机辅助几何设计、生物信息和医学成像的快

速发展

, 出现了越来越多的三维数字模型. 因此迫切需要有效的算法来表示、处理和使用

这些模型

. 计算共形几何在数字几何处理中扮演了一个重要角色. 它已经应用在很多重

要的领域

, 比如曲面修复、光顺、去噪、分片、特征提取、注册、重新网格化、网格样条转换、

动画和纹理合成

. 特别地, 共形几何奠定了曲面参数化的理论基础, 同时也提供了严格的

算法

. 计算共形几何还应用于计算机视觉中的人脸跟踪、识别和表情转换, 医学成像中的

脑电图、虚拟结肠镜和数据融合

, 几何建模中的具有任意拓扑流形上的样条构造.

共形几何之所以如此有用是基于以下一些事实

:

共形几何研究的是共形结构. 日常生活中的所有曲面都有一个自然的共形结构, 因

此共形几何算法非常普遍

.

共形结构比黎曼度量结构更灵活、比拓扑结构更具有刚性. 它能处理大量黎曼几何

不能有效处理的变换

, 这些变换还能保持很多拓扑方法会丢失的几何信息.

共形映射比较容易控制. 比如, 两个单连通封闭曲面之间的共形映射构成一个6 维

空间

, 因此只要固定3 个点, 这个映射就是唯一的. 这个事实使得共形几何方法在

曲面匹配和比较中非常有价值

.

共形映射保持局部形状, 因此在可视化方面有很好的应用.

所有的曲面都可以根据共形结构进行分类, 而且所有的共形等价类形成一个有限

维流形

. 这个流形有丰富的几何结构, 容易对其分析和研究. 与之相反, 曲面的等距

类形成一个难以分析处理的无穷维流形

.

计算共形几何

计算共形几何算法是以椭圆偏微分方程为基础的, 而椭圆偏微分方程又是容易求

解而且稳定的

, 因此计算共形几何方法对于实际工程应用非常有用.

共形几何中, 所有单连通曲面都能共形变换成某种标准空间: 球面、平面、双曲空间.

也就是说

, 任何曲面都具有三种标准几何(球几何、欧式几何、双曲几何) 中的一种.

这样大部分三维数字几何处理任务都能转化成二维标准空间中的任务

.

历史上

, 计算共形几何方法已经广泛应用于许多工程领域, 然而绝大部分应用都基

于平面区域的共形映射

. 最近, 随着数学理论的发展和计算能力的提升, 计算共形几何方

法已经从平面区域推广到具有任意拓扑的曲面

.

1.1

共形变换和共形结构

图

1: 共形映射保持角度

(a) Circle packing (b) Checkboard

图

2: 共形映射

根据

Fleix Klein 的Erlangen 纲领, 几何就是研究在特定的变换群下保持不变的空

间性质

. 共形几何就是研究保角变换群下的不变量. 它介乎于拓扑和黎曼几何之间.

计算共形几何

共形映射就是保角映射

, 如图1所示. 在无穷小邻域, 共形映射就是放缩变换. 它保

持局部形状

, 比如它将无穷小圆周映成无穷小圆周. 如图2所示, 这个bunny 曲面通过一

个共形映射映到平面

. 如果平面有一个circle packing, 则通过拉回得到bunny 曲面上的

一个

circle packing. 如果给平面铺上棋盘格, 则同样得到bunny 曲面的棋盘格修饰, 其中

直角和正方形都是保持的

.

曲面上的两个黎曼度量是共形的

, 如果它们定义的角度是相同的. 共形结构就是指

曲面上度量的共形等价类

, 而黎曼曲面就是带有共形结构的光滑曲面. 因此在黎曼曲面

上

, 我们可以度量角度, 但不能度量长度. 每一个带有度量的曲面都自动成为一个黎曼曲

面

.

如果两个黎曼曲面之间存在共形映射

, 则称它们是共形等价的. 显然, 共形等价是

黎曼曲面间的一个自然的等价关系

. 共形几何的目的就是在共形等价意义下对黎曼曲面

进行分类

, 这就是所谓的模空间问题. 给定一张光滑曲面, 考察它上面的所有共形结构在

共形等价下的模

, 这个集合被称为曲面的模空间. 对于具有正亏格的封闭曲面, 模空间是

正维数的有限维空间

.

1.2

基本任务

下面的问题是计算共形几何最基本的一些任务

. 这些问题是相互依赖的:

1.

共形结构

给定一张带有黎曼度量的曲面

, 计算它的内蕴共形结构的不同表示. 一种方法是计

算它的

Abelian 微分群, 另一种方法是计算标准的黎曼度量.

2.

共形模

完全共形不变量称为黎曼曲面的共形模

. 正如前面所讲的, 理论上存在一组有限的

数完全决定了黎曼曲面

, 这些称为黎曼曲面的共形模. 一个比较难的问题是显式计

算任意给定曲面的共形模

.

3.

标准黎曼度量

黎曼曲面的

uniformization 定理揭示了每一个黎曼度量都共形等价于一个常Gauss

曲率度量

. 除了球面和环面外, 这个度量是唯一的. 计算这个度量在计算共形几何

中具有基本的重要性

.

4.

共形映射

计算共形几何

计算两个共形等价的曲面之间的共形映射可以简化为计算它们到标准形状空间

(

球面、平面、双曲空间中的圆域) 之间的共形映射.

5.

拟共形映射

大部分微分同胚都不是共形的

, 它们将无穷小圆周映成无穷小椭圆. 如果这些椭

圆的长短轴比一致有界

, 那么就称为拟共形映射. 拟共形映射的微分是由所谓的

Beltrami

微分刻画的, Beltrami 微分记录了长轴方向和长短轴比. 有一个基本定理

是说通过

Beltrami 微分可以恢复拟共形映射. 而至于怎样通过Beltrami 微分计算

拟共形映射

, 则是一个具有很多应用价值的重要问题.

6.

共形镶嵌

粘合带边黎曼曲面并研究缝曲线形状和粘合样式之间的关系

. 这与拟共形映射问

题紧密相关

.

1.3

共形几何在工程应用中的优点

计算共形几何已经被证实在许多工程领域中有重要应用

. 下面是一些主要理由:

1.

标准区域

所有带度量的曲面都能共形地映成球面、平面或双曲圆盘中的标准区域

. 这可以帮

助我们将三维几何处理问题转化为二维问题

.

2.

通过曲率设计度量

每一个共形结构都有一个常

Gauss 曲率的标准度量, 这个度量在很多几何应用中

非常有价值

. 例如在双曲度量下, 每一个非平凡同伦类都有一个闭测地线代表元.

此外

, 我们可以根据预先给定的曲率设计黎曼度量, 这在几何建模中非常有用.

3.

一般几何结构

共形几何方法能够用来构造其他几何结构

, 比如仿射结构、射影结构等等. 这些结

构在几何建模应用中是关键的

.

4.

微分同胚的构造

共形映照和拟共形映照可以被用来构造曲面间的微分同胚

. 可以应用于曲面注册

和比较这些计算机视觉和医学图像中最基本的问题

.

计算共形几何

5.

等温坐标

共形结构可以被当作曲面上的等温坐标图册

. 在这种坐标下, 度量的表达式最简

单

, 因此所有的微分算子, 比如Laplace-Beltrami 算子, 具有很简洁的表达式. 这可

以用来简化偏微分方程

. 等温坐标保持局部形状, 对于可视化和纹理映射是非常完

美的

.

2

已有工作

图

3: 基本群的多边形表示

图

4: 四种类型的图. (a) A cut graph 但不是system of loops. (b) A system of loops. (c) 基本

群的基但不是

system of loops. (d) 同调基, 但既不是同伦基也不是cut graph.

计算共形几何已经有比较长的历史了

, 起初大部分共形几何方法都是针对平面区

域或拓扑圆盘的

. 直到近些年来才推广到具有复杂拓扑的曲面上, 这与当前研究热点计

算拓扑的发展是紧密相关的

. 有相当一部分计算共形算法是依赖于计算拓扑算法的.

计算共形几何

图

5: 从左到右: 输入模型, handle(绿) 和tunnel(红) 环, handle 特征

2.1

计算拓扑

计算拓扑的研究对象主要是单纯复形

, 比如三角网格曲面就是一种二维单纯复形.

计算拓扑的一些基本问题就是计算曲面单纯复形的

cut graph, 同调群和基本群. 知道了

cut graph,

就能将曲面剪开成拓扑圆盘, 这对于参数化和纹理映照是非常有用的. 知道了

基本群

, 就能完全确定封闭曲面的拓扑分类. 通常基本群是用多边形表示的, 其中有约化

多边形表示、标准多边形表示等一些特殊的多边形表示

, 见图3.

Vegter

和Yap[1] 给出了计算标准多边形表示的算法, Lazarus 等[2] 简化了Vegter 和

Yap

的算法, 复杂度为O(gn), 其中n; g 分别为曲面的大小和亏格. 标准多边形表示由2g

个具有公共点的环组成

, 令人不满意的是它们可能具有公共边. 在大部分应用中, 标准多

边形表示不是必须的

, 只需要知道cut graph 就足够了. cut graph 是指三角网格曲面上的

一族边集使得曲面去掉这些边后变成拓扑圆盘

, 如图4所示. Dey 和Schipper[3] 使用cut

graph

得到了检验曲线是否可缩或两曲线是否同伦的快速算法. 2002 年, Erickson 等[4]

第一次提出了最优

cut graph 的问题: 给每一条边赋一个权, 求权最小的cut graph. 这篇文

章证明了最小

cut graph 问题是NP 难的, 并给出了计算近似最小cut graph 的贪婪算法,

该算法复杂度为

O(g2n log n), 精度为O(log2g). de Verdièe 和Lazarus[5] 研究了一种称

为

"systerm of loops" 的特殊cut graph, 每一个systerm of loops 都由具有公共基点的2g 个

环组成

, 如图4所示. Erickson 等[6] 给出了一个简单的贪婪算法来计算基本群和第一同调

群的生成元

, 这同时也解决了de Verdièe 和Lazarus 提出了最短systerm of loops 问题.

计算共形几何

曲面上一些与特征紧密相关的环

, 比如handles 和tunnels, 在诸如拓扑修复、曲面

参数化和特征识别等应用中非常有用

, 如图5所示. Dey 等[7--9] 给出了计算handles 和

tunnels

的算法. Yin 等[10] 提出了使用universal covering space 来计算最短非平凡环的算

法

. de Verdièe[11] 使用最优pants 分解来找同伦类中的最短环. Xin 等[12] 研究了高亏格

曲面上的测地环

. 关于曲面上的非平凡环, 还有许多文章[13--19], 目前仍是一个热点问题.

(a)

调和1 形式(b) 共轭的调和1 形式

图

6: 调和1 形式

2.2

平面区域

传统的数值复分析方法集中在平面区域的共形映射

. [20--25] 作了详尽总结.

Schwarz-Christoffel

映射已经被广泛应用于计算共形映射[26,27]. [28--30] 研究了多连通

区域的

Schwarz-Christoffel 映射. [31] 给出了一种基于交比和Delaunay 三角化的鲁棒算

法

. 最近, Marshall 等[32] 引进了基于迭代简单映射的geodesic zippper 算法, Bishop[33]

提出了基于双曲几何的线性复杂度的共形映射算法

.

2.3

亏格为0 的曲面

[

34] 利用余切公式构造了离散调和映射, Léy 等[35] 引进了Cauchy-Riemann 方程

的一阶有限元逼近

. 2002 年, Desbrun 等[36] 最小化Dirichlet 能量得到了离散内蕴参数化.

Floater

[37] 引进平均值坐标来计算广义调和映射. [38, 39] 对拓扑球面的共形映射进行了

研究

. 在CG 领域, [40, 41] 对拓扑圆盘和球面上的共形映射进行了详尽地总结.

计算共形几何

2.4

高亏格曲面

高亏格曲面上共形结构的计算有两个主要方法

: 全纯微分方法和离散曲率流方法.

图

7: 全纯1 形式

2.4.1

全纯微分

离散全纯微分方法是由

Gu 和Yau[42,43] 提出的, 用来计算高亏格曲面上的共形结

构

. 这个方法基于Hodge 理论, 使用热扩散方法来计算每一个上同调类中的调和形式,

见图

6(a)和6(b). 然后利用Hodge 星算子构造全纯形式, 见图7. 所有计算都是在离散多边

形曲面上进行的

. Pinkall 等[34] 定义了一种不同的离散Hodge 星算子来计算极小曲面.

Mercat

[44] 通过离散Cauchy-Riemann 方程来构造离散全纯映射, 不过这个方法要求曲面

是四边形网格

. 2003 年, Hirani 在他的博士论文[45] 中详细介绍了离散外微分方法.

Gortler

等[46,47] 使用离散1 形式来对亏格为1 的曲面进行参数化.Tong 等[48] 推广

到带有锥奇点的

1 形式方法, 并用来进行remeshing 和tiling. 2009 年, Zeng 等[49,50] 将全

纯微分方法应用于计算带多个边界的亏格为

0 的曲面上的共形映射, 以及拟共形映射.

2.4.2 Ricci Flow

Ricci

流是由Hamilton[51] 在Princeton 的讨论班上引进的. Ricci 流对曲面和三维

流形的几何研究产生了革命性的影响

, 是当前几何研究中极为活跃的方向. 特别地,

计算共形几何

它导致了三维

Poincaré猜测的证明. Hamilton[52] 使用2 维Ricci 流给出了正亏格曲面

uniformization

定理的证明. 这表明了它在CG 领域中有极大的潜在应用价值.

图

8: Circle packing

存在很多方法离散光滑曲面

, 其中与共形映射离散特别相关的是由Thurston[53] 引

进的

circle packing 度量. circle packing 这个概念首先是由Koebe 提出的, Thurston 猜测平

面

Jordan 区域的circle packing 离散序列收敛于Riemann 映射, 见图8. 这个猜测被Rodin

和

Sullivan[54] 所证明.

Colin de Verdièe

[55] 建立了circle packing 的第一变分原理, 然后证明了Thurston 的

circle packing

度量存在性. 这为实现计算circle packing 度量的快速算法铺平了道路, 比

如

Collins 和Stephenson[56] 就给出了一个算法. Chow 和Luo[57] 推广了Colin de Verdièe

的工作

, 并引进了曲面上的离散Ricci 流和离散Ricci 能量. 它们证明了离散Ricci 流的一

般存在性和收敛性定理

, 同时证明了Ricci 能量的凸的. 基于此, Jin[58] 在2008 年给出了

离散

Ricci 流的算法实现.

另外一个相关的离散方法是

circle pattern, 它同时考虑网格曲面的组合与几何信

息

, 可以看成是circle packing 的变种. Circle pattern 是由Bowers 和Hurdal[59] 提出的, 已

经被证明是

Bobenko 和Springborn[60] 提出的凸能量的极小元. 2006 年, Kharevych 等[61]

给出了一个有效的

circle pattern 算法.

2.4.3 Yamabe Flow

Yamabe

问题目的是为紧Riemann 流形找到具有常标量曲率的共形度量. Yamabe[62]

给出了第一个带有漏洞的证明

, 之后被一些包括Trudinger[63], Aubin[64] 和Schoen[65] 在

内的研究者所更正

. 关于这个问题的详细总结可以参看Lee 和Parker 的文章[66].

2004

年, Luo[67] 研究了曲面上的离散Yamabe 流. 他引进了多边形度量的离散共形

计算共形几何

变换概念

, 这在研究离散Yamabe 流和相应的变分原理方面具有关键性的作用. 基于离散

共形类和几何方面的考虑

, Luo 定义离散Yamabe 能量为微分1 形式的积分, 然后证明了

这个能量是一个局部凸函数

. 他还从这得出Yamabe 流下的曲率发展是一个热方程.

最近

, Springborn 等[68] 的一个非常漂亮的工作表明可以将Yamabe 能量和Milnor-

Lobachevsky

函数等同起来, 将曲率发展的热方程和余切Laplace 方程等同起来. 近期Gu

等

[69] 使用离散Yamabe 能量构造了一个计算离散共形度量的有效算法. Bobenko 等[70]

讨论了离散双曲

Yamabe 流, 它被Zeng 等[71] 用来计算双曲结构和标准同伦群生成元.

图

9: 全局共形的纹理映照

图

10: 使用特殊的平坦度量设计向量场

2.5

应用

2.5.1

图形学

共形几何方法广泛应用于

CG 中. 等温坐标对于全局共形参数化来说是很自然

的

[42]. 因为共形映照不会扭曲局部形状, 所以它对于纹理映照来说是非常理想的. 图9显

示了一个使用全纯微分进行纹理映照的例子

. 特殊的平坦度量对于设计曲面上的向量场

是非常有价值的

, 图10显示了使用曲率流方法设计的向量场.

计算共形几何

图

11: 流形样条框架

2.5.2

几何建模

几何建模中的一个最基本的问题就是将传统的欧式区域上的样条系统地推广到流

形区域上

, 这与曲面上的一般几何结构关系紧密, 见图11和12.

传统的样条方案是建立在仿射不变量上的

, 如果流形具有仿射结构, 那么传统的样

条也能直接推广到流形上

. 然而由于拓扑障碍, 一般的流形不具有仿射结构. 但是删去一

些奇点后

, 曲面上允许存在仿射结构. 详细的讨论请参考Gu 等[72].

仿射结构可以通过共形几何方法显式计算

. 比如可以通过曲率流和全纯微分方法

来计算仿射结构

, 图13显示的是用曲率流方法构造的仿射结构. 与其他的方法比较起来,

比如基于平凡联络的方法

[73], 这些方法的优点是它能给出样条曲面的全局共形参数化,

即等温坐标

. 在这种坐标下, 微分算子, 比如梯度算子和Laplace-Beltrami 算子, 具有最简

单的形式

.

2.5.3

医学成像

共形几何在医学成像的很多领域都有应用

. 比如在脑电图中, 不同部分的大脑皮层

曲面片的注册是关键性的

. 大脑表面高度卷曲, 而且不同的人的大脑有不同的解剖结构,

计算共形几何

图

12: 流形样条

图

13: 仿射结构

因此在大脑皮层曲面片之间找到好的匹配是非常有挑战性的任务

. 图14演示了一个解决

方案

[39], 先通过用标准方式将大脑表面映到球面, 然后找到球面的自同构, 这样曲面片

的注册就很容易建立了

.

2.5.4

视觉

曲面匹配在计算机视觉中是一个基本问题

. 图15演示了曲面匹配的基本框架.

图

16演示了同一个人的不同表情的人脸匹配的例子, 细节可参考[74--76].Teichmüler 理论

可以应用于曲面分类

[77,78]. 通过使用Ricci 曲率流, 我们可以计算双曲uniformization 度

量

. 然后我们使用测地线进行pants 分解并计算Fenchel-Nielsen 坐标. 图17演示了万有覆

盖空间在双曲空间中的一个有限部分的计算

, 图18演示了计算Teichmüler 坐标的流程.

计算共形几何

图

14: 大脑表面的共形映照

图

15: 曲面匹配框架

2.5.5

计算几何

在计算几何中

, 同伦检测是一个重要的问题. 可以使用Ricci 流计算双曲uniformization

度量

[71]. 根据Gauss-Bonnet 定理, 每一个同伦类中有唯一的闭测地线. 给定一个环,

我们可以计算这个环的同伦类对应的

Möius 变换, 这个变换的轴就是双曲度量下的闭

测地线

. 如图19所示, 同伦的环的标准代表元是相同的.

计算共形几何

图

16: 不同表情的人脸匹配

图

17: 万有覆盖空间在双曲空间中的有限部分

3

总结

计算共形几何是一门数学和计算机科学的交叉学科

, 它对数学理论的掌握要求比

较高

. 很多算法都依赖于拓扑算法, 与计算拓扑紧密相关. 本文介绍了这个方向的一些基

本问题、算法以及应用

. 目前仍然有很多基本问题没有解决, 它们需要更深刻的理解和更

强大精确的计算方法

. 下面列举一些对理论和应用都非常重要的问题.

1. Teichmüler

映射

给定两个度量曲面和映射同伦类

, 计算唯一的angle distortion 最小的映射, 也就是

Teichmüler

映射.

计算共形几何

图

18: Teichmüler 空间中的Fenchel-Nielsen 坐标

图

19: 使用双曲度量进行同伦检测

2. Abel

微分

计算不同类型的

Abel 微分群, 特别是全纯的二次微分.

3.

组合结构和共形结构之间的关系

给定一个拓扑曲面

, 每一个三角化都有一个由circle packing 决定的自然的共形结

构

, 讨论这两个结构之间的关系.

4.

逼近理论

尽管计算共形不变量的算法已经有了

, 但是逼近的理论结果仍没有建立. 对于平面

区域的共形映射

, 不同离散方法的收敛性都已经建立了. 但是对于一般曲面而言,

收敛性分析仍然是开放的

.

5.

精度和稳定性

双曲几何计算对于数值误差是非常敏感的

. 要提高计算精度是非常具有挑战性的.

计算几何中的精确计算方法给出了解决这个问题的方向

. 在逆距离circle packing

计算共形几何

方法和组合

Yamabe 流方法中, 可接受曲率空间的非凸性造成了算法的不稳定. 因

此

, 曲面需要高精度的三角化. 在实际应用中, 提高三角化精度对这些算法是非常

重要的

. 交角为锐角的circle packing 算法更加稳定, 全纯微分方法最稳定.

计算共形几何

参考文献

[1] Vegter, G., Yap, C.K., 1990. Computational complexity of combinatorial surfaces. In: Proceedings

of the sixth annual symposium on Computational geometry. New York: ACM, 102-111.

[2] Lazarus, F., Pocchiola, M., Vegter, G., et al, 2001. Computing a canonical polygonal schema of an

orientable triangulated surface. In: SCG '01: Proceedings of the seventeenth annual symposium on

Computational geometry. New York: ACM, 80-89.

[3] Dey, T.K., 1994. A new technique to compute polygonal schema for 2-manifolds with application

to null-homotopy detection. In: Proceedings of the tenth annual symposium on Computational

geometry. New York: ACM, 277-284.

[4] Erickson, J., Har-Peled, S., 2002. Optimally cutting a surface into a disk. In: SCG '02: Proceedings

of the eighteenth annual symposium on Computational geometry. New York: ACM, 244-253.

[5] de Verdièe, E.C., Lazarus, F., 2002. Optimal system of loops on an orientable surface. In: Proc.

43rd Annual IEEE Symp. Foundations of Computer Science. Springer-Verlag 627-636.

[6] Erickson, J., Whittlesey, K., 2005. Greedy optimal homotopy and homology generators. In: SODA

'05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia,

PA, USA: Society for Industrial and Applied Mathematics, 1038-1046.

[7] Dey, T.K., Li, K., Sun, J., 2007. On computing handle and tunnel loops. In: CW '07: Proceedings

of the 2007 International Conference on Cyberworlds. Washington, DC, USA: IEEE Computer

Society, 357-366.

[8] Dey, T.K., Li, K., Sun, J., et al, 2008. Computing geometry-aware handle and tunnel loops in 3d

models. In: SIGGRAPH '08: ACM SIGGRAPH 2008 papers. New York: ACM, 1-9.

[9] Dey, T.K., Li, K., Sun, J., 2009. Computing handle and tunnel loops with knot linking. Comput.

Aided Des., 41(10): 730-738.

[10] Yin, X., Jin, M., Gu, X., 2007. Computing shortest cycles using universal covering space. Vis.

Comput., 23(12): 999-1004.

[11] Verdièe, E.C.D., Lazarus, F., 2007. Optimal pants decompositions and shortest homotopic cycles

on an orientable surface. J. ACM, 54(4): 18.

[12] Xin, S.Q., He, Y., Fu, C.W., et al, 2011. Euclidean geodesic loops on high-genus surfaces applied

to the morphometry of vestibular systems. In: MICCAI'11: Proceedings of the 14th international

conference on Medical image computing and computer-assisted intervention. Berlin, Heidelberg:

Springer-Verlag, 384-392.

[13] Chambers, E.W., Erickson, J., Worah, P., 2008. Testing contractibility in planar rips complexes. In:

SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry. New

York: ACM, 251-259.

[14] Chambers, E.W., Erickson, J., Nayyeri, A., 2009. Minimum cuts and shortest homologous cycles.

In: SCG '09: Proceedings of the 25th annual symposium on Computational geometry. New York:

ACM, 377-385.

[15] Chambers, E.W., Erickson, J., Nayyeri, A., 2009. Homology flows, cohomology cuts. In: STOC

计算共形几何

'09: Proceedings of the 41st annual ACM symposium on Theory of computing. New York: ACM,

273-282.

[16] Erickson, J., 2010. Maximum flows and parametric shortest paths in planar graphs. In: SODA

'10: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms.

Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 794-804.

[17] Erickson, J., Worah, P., 2010. Computing the shortest essential cycle. Discrete Comput. Geom.,

44(4): 912-930.

[18] Dey, T.K., Hirani, A.N., Krishnamoorthy, B., 2010. Optimal homologous cycles, total unimodularity,

and linear programming. In: STOC '10: Proceedings of the 42nd ACM symposium on Theory

of computing. New York: ACM, 221-230.

[19] Erickson, J., 2011. Shortest non-trivial cycles in directed surface graphs. In: SoCG '11: Proceedings

of the 27th annual ACM symposium on Computational geometry. New York: ACM, 236-243.

[20] Delillo, T.K., 1994. The accuracy of numerical conformal mapping methods: A survey of examples

and results. SIAM Journal on Numerical Analysis, 31(3): pp.788-812.

[21] Ivanov, M., V. T, 1995. Handbook of conformal mapping with computer-aided visualization. Boca

Raton: CRC Press.

[22] Binder, I., Braverman, M., Yampolsky, M., 2007. On the computational complexity of the riemann

mapping. ARKIV FOR MATEMATIK, 45(2): 221-239.

[23] Trefethen, L., 1986. Numerical conformal mapping. Amsterdam: North-Holland Publishing Co.

[24] Wegmann, R., 2005. Handbook of Complex Analysis: Geometric Function Theory. vol 2. Amsterdam:

Elsevier, 351-477.

[25] Henrici, , 1993. Discrete Fourier Analysis, Cauchy Integrals, Construction of Conformal Maps,

Univalent Functions. vol 3. London: Wiley.

[26] Driscoll, T.A., Trefethen, L.N. 2002. Schwarz-Christoffel Mapping. Cambridge Press.

[27] Banjai, L., Trefethen, L.N., 2003. A multipole method for schwarz--christoffel mapping of polygons

with thousands of sides. SIAM J. Sci. Comput., 25(3): 1042-1065.

[28] DeLillo, T.K., Elcrat, A.R., Pfaltzgraff, J.A., 2001. Schwarz-christoffel mapping of the annulus.

SIAM Review, 43(3): pp.469-477.

[29] Delillo, T., Elcrat, A., Pfaltzgraff, J., 2004. Schwarz-christoffel mapping of multiply connected

domains. Journal d'Analyse Mathéatique, 94: 17-47.

[30] Crowdy, D., 2005. The schwarz-christoffel mapping to bounded multiply connected polygonal

domains. Proceedings: Mathematical, Physical and Engineering Sciences, 461(2061): pp.2653-

2678.

[31] Driscoll, T.A., Vavasis, S.A., 1998. Numerical conformal mapping using cross-ratios and delaunay

triangulation. SIAM J. Sci. Comput., 19: 1783-1803.

[32] Marshall, D.E., Rohde, S., 2007. Convergence of a variant of the zipper algorithm for conformal

mapping. SIAM J. Numer. Anal., 45: 2577-2609.

计算共形几何

[33] Bishop, C.J., 2010. Conformal mapping in linear time. Discrete Comput. Geom., 44: 330-428.

[34] Pinkall, U., Polthier, K., 1993. Computing discrete minimal surfaces and their conjugates. Experimental

Mathematics, 2: 15-36.

[35] Léy, B., Petitjean, S., Ray, N., et al, 2002. Least squares conformal maps for automatic texture atlas

generation. In: Proceedings of the 29th annual conference on Computer graphics and interactive

techniques. New York: ACM, 362-371.

[36] Desbrun, M., Meyer, M., Alliez, P., 2002. Intrinsic parameterizations of surface meshes. Computer

Graphics Forum, 21(3): 209-218.

[37] Floater, M.S., 2003. Mean value coordinates. Comput. Aided Geom. Des., 20: 19-27.

[38] Gotsman, C., Gu, X., Sheffer, A., 2003. Fundamentals of spherical parameterization for 3d meshes.

In: SIGGRAPH '03: ACM SIGGRAPH 2003 Papers. New York: ACM, 358-363.

[39] Gu, X., Wang, Y., Chan, T.F., et al, 2004. Genus zero surface conformal mapping and its application

to brain surface mapping. IEEE Transactions on Medical Imaging, 23: 949-958.

[40] Floater, M.S., Hormann, K., 2005. Surface parameterization: a tutorial and survey. In: Dodgson,

N.A., Floater, M.S., Sabin, M.A.. Advances in multiresolution for geometric modelling. Springer

Verlag, 157-186.

[41] Sheffer, A., Praun, E., Rose, K., 2006. Mesh parameterization methods and their applications.

Found. Trends. Comput. Graph. Vis., 2: 105-171.

[42] Gu, X., Yau, S.T., 2003. Global conformal surface parameterization. In: SGP '03: Proceedings

of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing. Aire-la-Ville,

Switzerland, Switzerland: Eurographics Association, 127-137.

[43] Jin, M., Wang, Y., Yau, S.T., et al, 2004. Optimal global conformal surface parameterization.

In: VIS '04: Proceedings of the conference on Visualization '04. Washington, DC, USA: IEEE

Computer Society, 267-274.

[44] Mercat, C., 2001. Discrete riemann surfaces and the ising model. Communications in Mathematical

Physics, 218: 177-216.

[45] Hirani, A.N., 2003. Discrete exterior calculus. PhD thesis. Pasadena, CA, USA: California Institute

of Technology.

[46] Gortler, S.J., Gotsman, C., Thurston, D., 2006. Discrete one-forms on meshes and applications to

3d mesh parameterization. Comput. Aided Geom. Des., 23: 83-112.

[47] Tewari, G., Gotsman, C., Gortler, S.J., 2006. Meshing genus-1 point clouds using discrete oneforms.

Computers and Graphics, 30: 917-926.

[48] Tong, Y., Alliez, P., Cohen-Steiner, D., et al, 2006. Designing quadrangulations with discrete

harmonic forms. In: Proceedings of the fourth Eurographics symposium on Geometry processing.

Aire-la-Ville, Switzerland, Switzerland: Eurographics Association, 201-210.

[49] Zeng, W., Yin, X., Zhang, M., et al, 2009. Generalized koebe's method for conformal mapping

multiply connected domains. In: SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and

计算共形几何

Physical Modeling. New York: ACM, 89-100.

[50] Zeng, W., Luo, F., Yau, S.T., et al, 2009. Surface quasi-conformal mapping by solving beltrami

equations. In: Proceedings of the 13th IMA International Conference on Mathematics of Surfaces

XIII. Berlin, Heidelberg: Springer-Verlag, 391-408.

[51] Hamilton, R., 1982. Three manifolds with positive ricci curvature. J. Differ. Geom., 17: 255-306.

[52] Hamilton, R., 1988. Mathematics and General Relativity. vol 71. American Mathematical Society.

[53] Thurston, W., 1980. Geometry and Topology of Three-Manifolds. Princeton University Press.

[54] Rodin, B., Sullivan, D., 1987. The convergence of circle packings to the riemann mapping. J.

Differ. Geom., 26(2): 349-360.

[55] Colin de Verdièe, Y., 1991. Un principle variationnel pour les empilements de cercles. Invent.

Math., 104(3): 655-669.

[56] Collins, C.R., Stephenson, K., 2003. A circle packing algorithm. Comput. Geom. Theory Appl.,

25: 233-256.

[57] Chow, B., Luo, F., 2003. Combinatorial ricci flows on surfaces. J. Differ. Geom., 63(1): 97-129.

[58] Jin, M., Kim, J., Luo, F., et al, 2008. Discrete surface ricci flow. IEEE Transactions on Visualization

and Computer Graphics, 14(5): 1030-1043.

[59] Bowers, P.L., Hurdal, M.K., 2003. Planar conformal mappings of piecewise flat surfaces. In: In Visualization

and Mathematics III, H.-C. Hege and K. Polthier, Eds. Mathematics and Visualization.

Springer-Verlag 3-34.

[60] Bobenko, A.I., Springborn, B.A., 2004. Variantional principles for circle patterns and koebe's

theorem. Trans. Am. Math. Soc., 356: 659-689.

[61] Kharevych, L., Springborn, B., Schröer, P., 2006. Discrete conformal mappings via circle patterns.

ACM Trans. Graph., 25: 412-438.

[62] Yamabe, H., 1960. The yamabe problem. Osaka Math. J., 12(1): 21-37.

[63] Trudinger, N., 1968. Remarks concerning the conformal deformation of riemannian structures on

compact manifolds. Ann. Scuola Norm. Sup. Pisa, 22(2): 265-274.

[64] Aubin, T., 1976. éuations diffrétielles non linéires et problèe de yamabe concernant la courbure

scalaire. J. Math. Pure Appl., 55(3): 269-296.

[65] Schoen, R., 1984. Conformal deformation of a riemann metric to constant scalar curvature. J.

Differ. Geom., 20(2): 479-495.

[66] Lee, J.M., Parker, T.H., 1987. The yamabe problem. Bull. Am. Math. Soc., 17(1): 39-71.

[67] Luo, F., Khan, L., Bastani, F., et al, 2004. A dynamically growing self-organizing tree (dgsot) for

hierarchical clustering gene expression profiles. Bioinformatics, 20(16): 2605-2617.

[68] Springborn, B., Schröer, P., Pinkall, U., 2008. Conformal equivalence of triangle meshes. In:

SIGGRAPH Asia '08: ACM SIGGRAPH ASIA 2008 courses. New York: ACM, 1-11.

[69] Yin, X., Jin, M., Luo, F., et al, 2009. Emerging trends in visual computing. In: . Berlin, Heidelberg:

计算共形几何

Springer-Verlag, 38-74.

[70] Bobenko, A., Springborn, B., Pinkall, U., 2010. Discrete conformal maps and ideal hyperbolic

polyhedra. arXiv:1005.2698.

[71] Zeng, W., Jin, M., Luo, F., et al, 2009. Canonical homotopy class representative using hyperbolic

structure. In: Proc. IEEE Int. Conf. Shape Modeling and Applications SMI 2009. 171-178.

[72] Gu, X., He, Y., Qin, H., 2006. Manifold splines. Graph. Models, 68(3): 237-254.

[73] Crane, K., Desbrun, M., Schröer, P., 2010. Trival connections on discrete surfaces. Comput.

Graph. Forum, 29(5): 1525-1533.

[74] Wang, S., Wang, Y., Jin, M., et al, 2007. Conformal geometry and its applications on 3d shape

matching, recognition, and stitching. IEEE Trans. Pattern Anal. Mach. Intell., 29(7): 1209-1220.

[75] Zeng, W., Zeng, Y., Wang, Y., et al, 2008. 3d non-rigid surface matching and registration based

on holomorphic differentials. In: ECCV '08: Proceedings of the 10th European Conference on

Computer Vision. Berlin, Heidelberg: Springer-Verlag, 1-14.

[76] Zeng, W., Samaras, D., Gu, D., 2010. Ricci flow for 3d shape analysis. IEEE Trans. Pattern Anal.

Mach. Intell., 32(4): 662-677.

[77] Zeng, W., Lui, L.M., Gu, X., Yau, S.T., 2008. Shape analysis by conformal modules. Methods

Appl. Anal., 15(4): 539-556.

[78] Jin, M., Zeng, W., Ning, D., Gu, X., 2009. Computing fenchel-nielsen coordinates in teichmüler

shape space. In: IEEE International Symposium on Information Processing in Sensor Networks.

121-132.