伪三角剖分性质的研究

摘要

三角剖分与伪三角剖分是计算几何领域中的重要课题，它具有广泛的应用价值.人们在三角剖分方面的研究日趋完善，而在伪三角剖分(于20世纪90年代，由Pocchiola和Vegter提出)方面的研究尚不完善。本文研究了伪n边形最小伪三角剖分数的上下界。由于伪三角剖分理论与方法可应用到机器人手臂动作设计、动力学碰撞检测、计算机图形学、曲面重构以及有限元网格生成等问题，因此伪三角剖分数范围的改进有一定的实际应用价值。在文献Pseudo-Triangulations-a Survey中，Rote、Santos和Streinu指出伪n边形的最小伪三角剖分数的范围是[2n-3，h(n-1)](其中h(n)为Catalan数)，但对于一般的伪n边形来说，此界限相对宽松。在分析并讨论了伪n边形的若干性质后，本文对Rote等人给出的上下界展开改进工作。 ㈠利用凸n边形与伪n边形间存在的对偶图同构关系，将伪n边形的最小伪三角剖分数分为二个组成部分，即基本剖分数(A(k)和特殊剖分数(B).在引入伪n边形的受限对角线(用k表示受限对角线条数)概念后，利用容斥原理求出伪n边形的基本剖分数。在分析并总结伪n边形的特殊剖分的性质后，找到使特殊剖分达到最大值的伪n边形的形状，并求出了最大值。 ㈡指出了伪n边形的基本剖分数、特殊剖分数随k值变化而变化的情况，于是根据k的不同取值，并利用基本剖分数与特殊剖分数改进Rote等人给出的上下界：当o≤k≤[n/2]时，剖分数的范围是[A(k)，h(n-1)](此处A(k)大于2n-3)；当[n/2]≤k≤(n-3)(n-4)/2时，剖分数的范围是[2n-3，A(k)+∑[k/2]m=1B(m)](此处A(k)+∑[k/2]m=1B(m)至多是h(n-1)的0.67倍，明显优于Rote等人给出的上界。

目录

文摘

英文文摘

声明

第1章绪论

1.1引言

1.2相关研究的发展和现状

1.2.1 Delaunay三角剖分方面

1.2.2平面线段集三角剖分方面

1.2.3平面点线集三角剖分方面

1.2.4多边形三角剖分方面

1.2.5伪三角剖分方面

1.3本文研究内容与安排

第2章基本概念和性质

2.1基本概念与记号

2.2(伪)三角剖分的定义及相关性质

2.2.1定义

2.2.2性质

第3章凸n边形三角剖分与伪n边形伪三角剖分的联系

3.1对偶图同构

3.2伪n边形与凸n边形在剖分上的对应

3.2.1对应规则

3.2.2对应规则的局限性

第4章伪n边形的最小伪三角剖分数

4.1受限对角线

4.2伪n边形的基本剖分

4.3伪n边形的特殊剖分

4.4特殊剖分数的最大值

4.4.1 n为偶数的情况

4.4.2 n为奇数的情况

第5章结束语

5.1本文研究的主要工作

5.2待研究的问题

参考文献

致 谢