（应用数学专业论文）伪三角剖分性质的研究.pdf

中文摘要 摘要 三角剖分与伪三角剖分是计算几何领域中的重要课题，它具有广泛的应用价 值人们在三角剖分方面的研究日趋完善，而在伪三角剖分( 于2 0 世纪9 0 年代，由 p o c c h i o l a 和v e 垂e r 提出 1 , 2 1 ) 方面的研究尚不完善 本文主要研究了伪挖边形最小伪三角剖分数的上下界由于伪三角剖分理论 与方法可应用到机器人手臂动作设计、动力学碰撞检测、计算机图形学、曲面重 构以及有限元网格生成等问题，因此伪三角剖分数范围的改进有一定的实际应用 价值 在文献p s e u d o - t r i a n g u l a t i o n s - as u r v e y ( c o n t e m p o r a r ym a t h e m a t i c s ，o c t ，2 0 0 7 ) 中，r o t e 、s a n t o s 和s t r e i n u 指出伪押边形的最小伪三角剖分数的范围是 厂2 ”3 ， 一1 ) ( 其中乃( 玎) 为c a t a l a n 数) 但对于一般的伪刀边形来说，此界限相 对宽松在分析并讨论了伪n 边形的若干性质后，本文对r o t e 等人给出的上下界 展开改进工作 首先，利用凸n 边形与伪n 边形间存在的对偶图同构关系，将伪”边形的最 小伪三角剖分数分为二个组成部分，即基本剖分数口( 助) 和特殊剖分数) 在引入 伪n 边形的受限对角线( 用k 表示受限对角线条数) 概念后，利用容斥原理求出伪n 边形的基本剖分数在分析并总结伪聆边形的特殊剖分的性质后，找到使特殊剖 分达到最大值的伪刀边形的形状，并求出了最大值 其次，本文指出伪珂边形的基本剖分数、特殊剖分数随后值变化而变化的情 况，于是根据k 的不同取值，并利用基本剖分数与特殊剖分数改进r o t e 等人给出 的上下界：当o k _ l n 2 d 时，剖分数的范围是陋( 后) ，h ( n - 1 ) 】( 此处么( 幼大于2 - 3 ) ； 当b 2 j 七 3 时，点集的最小伪三角剖分数大于等于j l i p 一2 ) 4 柑( 这 里严i c i ) 文献 3 2 】还列举了当3 ”1 0 ，3 c 1 0 时，点集的最小伪三角剖分数 ( 1 3 ) 其他方面k e t t n e r 等人在文献 3 3 1 中证明了每一个平面刀点集( 无三点共线) 都 有一个最小伪三角剖分，其顶点最大度是5 ，最大面度是4 ，且这两个度的界限都是紧致 的2 0 0 0 年，s t r e i n u 在文献 3 4 】中提到了伪三角剖分在机器人手臂动作设计中的应用 2 0 0 2 年，s a r i e lh a r p e l e d 在文献 3 5 1 中介绍了三维空间中的点集伪三角剖分。2 0 0 7 年， s a n t o s 在文献 3 】中系统地阐述了伪三角剖分方面的知识，包括伪三角剖分的基本性质、 点集的伪三角剖分、多边形的伪三角剖分、多面体的伪三角剖分等等，文献 3 】中也介绍 了三维空间中点集的伪三角剖分方面的内容2 0 0 7 年，g u d m u n d s s o n 在文献【3 6 】中讨论 了最小权伪三角剖分问题等等 ( 2 ) 平面多边形伪三角剖分方面 相关研究刚刚开始，r o t e 等人在文献 3 】中对相关研究做了综述，并证明了伪f 边形 的最小伪三角割分数范围是l2 n - 3 , 办( 船一1 ) i 通过阅读文献不难看出，目前无论国内还是国外，对伪三角剖分方面问题的研究主 要基于平面点集，而对一般多边形的伪三角剖分研究得很少因此本文主要研究的伪刀 边形最小伪三角剖分方面的问题，将会存在一定的研究空间，同时也有重要的理论意义 和应用价值总之伪三角剖分仍有一定的空白领域值得人们去探索 1 3 本文研究内容与安排 本文主要研究的是伪1 边形的最小伪三角剖分数，从凸n 边形三角剖分与伪”边形 的最小伪三角剖分间的联系入手，确定伪”边形的最小伪三角剖分数的范围 第l 章，绪论简单介绍了三角剖分与伪三角剖分问题的发展及其应用，以及本论 文的内容安排 第2 章，基本概念和性质介绍了三角剖分与伪三角剖分的一些相关定义和性质 5 绪论 第3 章，研究并讨论了凸n 边形三角剖分与伪玎边形伪三角剖分的联系，利用这种 联系提出了伪刀边形的最小伪三角剖分数的求法 第4 章，伪刀边形的最小伪三角剖分数给出求一般伪胛边形的基本剖分数算法、 特殊剖分数算法、最小伪三角剖分数算法，并找到使特殊剖分达到最大值的伪n 边形的 形状，求出最大值，以此构造最小伪三角剖分数的上下界 第5 章，结论对本文的内容进行了总结，指出了研究工作中需要进一步研究的问 题，并对未来的工作进行了展望 6 伪三角剖分性质的研究 第2 章基本概念和性质 本章第1 节主要介绍全文所使用的基本概念和记号，其中大部分引自文献【3 ，3 0 1 ， 一部分引自文献 3 7 】第2 节介绍三角剖分和伪三角剖分的定义和相关性质 2 1 基本概念与记号 定义2 1 3 0 1 如果一个多边形恰好有3 个凸的顶点，其它顶点均为凹点，这样的多 边形称为伪三角形 定义2 2 t 3 】如果一个多边形恰好有疗个凸的顶点，其它顶点均为凹点，这样的多边 形称为伪，2 边形 定义2 3 1 3 7 】多边形相邻两个顶点间的直线段称为多边形的边伪n 边形相邻的两 个凸顶点间的凹链称为伪n 边形的一个侧，即伪n 边形有7 1 个侧 记号： 对某一个伪，z 边形尸，取( p ) ( 在不致混淆的情况下简记为巩) 表示这个伪n 边 形的最小伪三角剖分；& 。( p ) ( 在不致混淆的情况下简记为。) 表示这个伪胛 边形的所有最小伪三角剖分构成的集合；s 品。为s 矿。的子集，使得s 。中任意一 元素的对偶图每一个节点的度均不超过3 对某一个凸刀边形丁，瓦表示丁的三角剖分，品。表示丁的所有三角剖分所构 成的集合 本文用办仍) 表示c a t a l a n 数： = n 1r i , 2 n 珂- 一1 2 、) 。c a t a l a n 数是凸疗边形的三角剖分数j 7 基本概念和性质 2 2 ( 伪) 三角剖分的定义及相关性质 2 2 1 定义 定义2 4 t 3 4 1 对一个伪刀边形用若干对角线进行剖分，这些对角线只能在多边形顶 点处相交，剖分后产生若干伪三角形，且这些伪三角形互不相交，即为伪，z 边形的伪三 角剖分 定义2 5 3 1 图g ( 任意三点不共线) 中的顶点p 称为尖, 点( p o i n t e d ) ，如果图g 中与点 p 所有关联的边都在一个半平面内，则这样的点p 称为尖点 定义2 6 【3 4 】用最少的对角线对伪疗边形进行伪三角剖分，这样的剖分称为伪船边 形的最小伪三角剖分( 有时也称为尖点伪三角剖分，因为这样剖分后，每一个顶点都是 尖点) 2 2 2 性质 凸，z 边形与伪刀边形的基本性质对比，如表2 1 所示，其中伪，z 边形的剖分指最小 伪三角剖分 表2 1 凸甩边形与伪甩边形的基本性质对比 t a b 2 1ac o n t r a s tb e t w e e nc o n v e x 疗一g o na n dp s e u d o 力- g o ni nf u n d a m e n t a lp r o p e r t i e s 凸顶点凹顶点剖分所用对角线条数剖分出的单元个数 凸，2 边形 刀0 一3 门一2 ( 个三角形) 伪，z 边形 ，2 任意多个 胛一3 n - - 2 ( 个伪三角形1 此外，对凸刀边形进行三角剖分，对伪，z 边形进行最小伪三角剖分，它们都有各自 的尖点生成树做为自己的生成子图 4 0 , 4 1 , 4 2 对平面 点集( 无三点共线) 进行的三角剖分与最小伪三角剖分，剖分后都有2 玎一3 条边，分别产生玎一2 个三角形和玎一2 个伪三角形 对平面，z 点集，当点集处于凸位置时，其三角剖分数与最小伪三角剖分数均为c a t a l a n 数；当点集处于任意位置时，其三角剖分数的下界为2 3 3 ”，上界为4 3 ” 3 1 8 伪三角剖分性质的研究 第3 章凸n 边形三角剖分与伪n 边形伪三角剖分的联系 凸n 边形三角剖分方面的研究成果颇丰，如对角线翻转距离1 1 3 , 4 3 、三角剖分图及三 角剖分树【1 2 1 、三角剖分的优化算法 4 4 1 等等，而对伪，l 边形的伪三角剖分的研究初始于 上世纪9 0 年代，在文献【3 】中作者对伪三角剖分方面的知识作了系统的阐述，但对伪刀 边形的最小伪三角剖分介绍得并不详细，凸刀边形的三角剖分与伪n 边形的最小伪三角 剖分之间的联系除了在2 2 2 节中介绍的几个简单性质对比，其它的联系如本章所述 3 1 对偶图同构 在鼢。中任意取一元素，可在墨。中找到一个( 或几个) 元素，使得它们的对偶图同构 如下面的例图所示，伪n 边形与凸n 边形剖分后，存在同构的对偶图伪刀边形的 剖分指最小伪三角剖分 9 凸r 边形三角剖分与伪y 边形伪三角剖分的联系 ( 1 ) 伪6 边形 ( 1 ) p s e u d o6 - g o n ( 3 ) 对角线b 翻转成b ( 3 ) d i a g o n a lbf l i p si m ob ( 2 ) 对角线a 翻转成a ( 2 ) d i a g o n a laf l i p si n t oa ( 4 ) 对角线c 翻转成c ( 4 ) d i a g o n a lcf l i p si n t oc ( 5 ) 凸6 边形的四个三角剖分 ( 5 ) f o u ro fc o n v e x6 - g o nt r i a n g u l a t i o n s 图3 1 伪6 边形和凸6 边形 f i g 3 1p s e u d o6 - g o na n dc o n v e x6 - g o n 1 0 4 伪三角剖分性质的研究 ( 1 ) 伪7 边形 ( 1 ) p s e u d o7 - g o n ( 3 ) 对角线b 翻转成b ( 3 ) d i a g o n a lbf l i p si n t ob ( 2 ) 对角线a 翻转成a ( 2 ) d i a g o n a laf l i p si n t oa t ( 4 ) 对角线c 翻转成c ( 4 ) d i a g o n a lcf l i p si n t oc 黝2 3 4 1 囝- 觏。趣 666 ( 5 ) 凸7 边形的四个三角剖分 ( 5 ) f o u ro fc o n v e x7 - g o nt r i a n g u l a t i o n s 图3 1 伪7 边形和凸7 边形 f i g 3 1p s e u d o7 - g o na n dc o n v e x7 - g o n 6 凸刀边形三角剖分与伪刀边形伪三角剖分的联系 ( 1 ) 伪8 边形 ( 1 ) p s e u d o8 - g o n ( 3 ) 对角线b 翻转成b ( 3 ) d i a g o n a lbf l i p si n t ob ( 2 ) 对角线a 翻转成a ( 2 ) d i a g o n a l af l i p si n t oa ( 4 ) 对角线c 翻转成c ( 4 ) d i a g o n a lcf l i p si n t oc ( 5 ) 凸8 边形的四个三角剖分 ( 5 ) f o u ro fc o n v e x8 - g o nt r i a n g u l a t i o n s 图3 3 伪8 边形和凸8 边形 f i g 3 3p s e u d o8 - g o na n dc o n v e x8 - g o n 1 2 伪三角剖分性质的研究 在以上的几组例图中，我们可以看出凸力边形( 三角剖分) 和伪聆边形( 最小伪三角剖 分) 分别剖分后，存在对偶图同构的情况，于是有下面的定理 定理3 1 在s 靓中任意取一元素，可在中找到一元素，使得它们的对偶图同构， 反之不成立 证明：由于在s 品。中任意一元素的对偶为二叉树，而在品。中任意一元素的对偶图 也为二叉树，且s 矿。中元素个数小于等于s r 。中元素个数，那么s 。元素个数也将小于等 于s r 。中元素个数，根据s 。中某一元素找到品。中某几个元素，使得它们的对偶图同构 是可能的 对于一个伪6 边形，如图3 4 所示，在它所有的最小伪三角剖分中，对偶图只能是 一条路径，而对一个凸6 边形，其三角剖分的对偶图不只有路径，还有二叉树，因此定 理3 1 反之不成立 定理证毕 65 图3 4 最小伪三角剖分对偶图只能是路径的一个伪6 边形 f i g 3 4ap s e u d o6 - g o np o i n t e dt r i a n g u l a t i o n , w h i c hd u a lg r a p hc a l lo n l yb eap a t h 3 2 伪刀边形与凸，z 边形在剖分上的对应 伪门边形的最小伪三角剖分的对角线数目和凸r 边形三角剖分的对角线数目相同， 均为力一3 ，：且二者各自剖分后，伪三角形数目和三角形数目相同+ ，均为力一2 可以说 伪刀边形与凸刀边形在剖分上有一定的相近性，在已知凸刀边形三角剖分的前提下，利 用这种相近性来探索伪刀边形的剖分，是一个捷径目前关于凸边形三角剖分的算法 有很多，这同时也方便了伪, 边形的剖分 1 3 凸力边形三角剖分与伪r 边形伪三角剖分的联系 3 2 1 对应规则 现在我们可以按照凸疗边形三角剖分的过程，对一个伪刀边形进行最小伪三角剖分 例如，图3 5 所示，已知凸7 边形的一个三角剖分( 见图3 5 ( 1 ) ) ，对伪7 边形进行最小伪 三角剖分( 见图3 5 ( 2 ) ) 在凸7 边形的这个三角剖分中，根据对角线16 ，在伪7 边形中 可添上对角线a ，注意对角线a ，其一端点为顶点1 ，另一端点为距顶点6 稍近的一个凹 点( 由于点1 和点6 之间无法联结对角线，所以点6 可以用距离它稍近的一个凹点来代 替) 按照此对应规则，根据凸7 边形中的对角线14 ，可在伪7 边形中添上对角线b ， 根据对角线24 ，添上对角线c ，根据对角线46 ，可添上对角线d ，从而根据这个凸7 边形的三角剖分，我们完成了对这个伪7 边形的最小伪三角剖分 7 4 ( 1 ) 凸7 边形三角剖分( 2 ) 伪7 边形最小伪三角剖分 ( 1 ) ac o n v e x7 - g o nt r i a n g u l a t i o n( 2 ) ap s e u d o7 - g o np o i n t e dp s e u d o - t r i a n g u l a t i o n 图3 5 根据凸7 边形的三角剖分来剖分一个伪7 边形 f i g 3 5ap s e u d o7 - g o np o i n t e dp s e u d o - t r i a n g u l a t i o n , w h i c ha c c o r d i n gt oac o n v e x7 - g o nt r i a n g u l m i o n 3 2 2 对应规则的局限性 尽管伪n 边形的最小伪三角剖分可以按照3 2 1 节的对应规则得到，但并不意味着 所有形状的伪 边形的最小伪三角剖分都可按此对应规则得到，这种对应规贝【 有一定的 局限性 如图3 6 所示，根据图3 6 ( 1 ) 的凸7 边形三角剖分，无法完成图3 6 ( 2 ) 的伪7 边形的 最小伪三角剖分问题在于：根据凸7 边形的对角线73 ，在伪7 边形中构造不出相应 1 4 伪三角剖分性质的研究 的对角线如图3 6 ( 2 ) 虚线所示，7 j 显然不是对角线，虽然7 _ 3 、7 - 3 ”是对角线，但这 破坏了凹点3 、3 ”的尖点性，且不构成最小伪三角剖分j 因此根据凸7 边形的这个三角 剖分，无法完成这个伪7 边形的最小伪三角剖分，因此，这种对应规则有一定的局限性 2 ( 1 ) 凸7 边形三角剖分 ( 1 ) ac o n v e x7 - g o nt r i a n g u l a t i o n 4 7 ， 4 ( 2 ) 根据( 1 ) 而无法完成的伪7 边形最小伪三角剖分 ( 2 ) ap s e u d o7 - g o np o i n t e dp s e u d o - t r i a n g u l a t i o nc a n tb e c o m p l e t e d ，w h i c ha c c o r d i n gt o ( 1 ) 图3 6 对应规则的局限性 f i g 3 6t h el i m i t a t i o n so f t h ec o r r e s p o n d i n gr u l e s 了解这种对应规则的局限性后，我们知道伪n 边形的所有最小伪三角剖分，是不可 能仅仅通过这种与凸，z 边形三角剖分的对应而得到的对于一个伪n 边形，能与凸n 边 形三角剖分对应上的最小伪三角剖分实际上是s 品。中的元素，而对应不上的最小伪三角 剖分则是& 。一品行中的元素，因此要想得到这个伪1 , 边形最小伪三角剖分数，就得对 昂。一昂。中的元素性质做进一步的研究 1 5 伪，2 边形的最小伪三角剖分数 第4 章伪n 边形的最小伪三角剖分数 4 1 受限对角线 定义4 1 伪刀边形中，由于凹点及与凹点关联边的阻隔，导致某些对角线不能参 与最小伪三角剖分，我们把这样的对角线称作受限对角线 引理4 1 吲一般伪刀边形的最小伪三角剖分数的范围是 2 棚，九( 佗一1 ) ，且上下界均 可取到 也就是说昂。中元素个数大于等于2 ”3 ，小于等于c a t a l a n 数，而昌。中元素个数等 于c a t a l a n 数 若已知一凸n 边形的三角剖分，按3 2 1 节所述的对应规则，对一确定的伪”边形 进行最小伪三角剖分，期间会产生对应不上的情况，这种情况的产生根源于伪n 边形的 形状，由于其形状不同，导致某些条对角线不能参与剖分，从而导致伪疗边形的最小伪 三角剖分数也就不同不妨给每一个伪i 边形赋予一个指数k ，用来表示这个伪刀边形 中受限对角线数目 如图4 1 【3 】所示，这种形状的伪刀边形是产生受限对角线最多的情况，容易求出受 限对角线数目是后：( n - 3 ) ( 一n - 4 ) ，也就是说，对图4 1 进行最小伪三角剖分，将有 忌：鱼二掣条受限对角线 1 6 伪三角剖分性质的研究 1 图4 1 一个七：! ! 二! 丛竺二兰! 的伪n 边形 2 f i g 4 1ap s e u d o n - g o n w i t h 七：! 竺二1 2 1 1 = 1 2 2 对一般的伪聆边形来说，。后 o ，( n - 3 ) ( n - 4 ) 2 当k = 0 时，伪n 边形的最小伪三角剖分数为c a t a l a n 数： 坳枷= 击( 譬) 当七= 鱼半时，伪聆边形的最小伪三角剖分数为2 一 4 2 伪n 边形的基本剖分 定义4 2 对于一个伪n 边形，假设它有k 条受限对角线，根据3 2 1 节的对应规则， 得到的最小伪三角剖分，称作伪玎边形的基本剖分 一个伪n 边形的基本剖分数实际上是s 品。中元素的个数，在本文我们用彳( 幼表示一 个伪n 边形的基本剖分数 若已知一个伪n 边形有k 条受限对角线，利用3 2 1 节的对应规则，再借助容斥原 理，可以计算出这个伪刀边形的基本剖分数 1 7 伪，7 边形的最小伪三角剖分数 容斥原理：设s 是有限集合，置，b ，只是同集合s 有关的k 个性质，设么j 是s 中具有性质只的元素构成的集合( 1 i k ) ，石是s 中不具有性质只的元素的集合 ( 1 i 七) ，则s 中不具有性质只，最，只的元素个数为： 一an a 2n n z = i s 一j 4 i + 1 4n , 4 j i 一阻，n a jn a ，i + + j = l l ，2 ，( 1 ，2 ：- ，t ) 的2 组合的3 组合 ( 一1 ) 1 4n a 2n n 4 i 在这里，将伪刀边形中受限对角线依次标记为口。，口：，吼，那么i a ，i 表示在凸n 边形所有三角剖分中，对角线q 出现的次数；i 4n 4 i 表示在凸疗边形所有三角剖分中， 对角线口，和口，同时出现在一个三角剖分中的次数，等等网将表示凸刀边形三角剖分 数，即h ( n - 1 ) ，则任意一个伪珂边形的基本剖分数为： a ( k ) = h ( n - 1 ) 一1 4 l +f 4n4 i 一i 4n4 n 4 f + + ( 一1 ) 。1 4n a ：n na k l 闰 敬缮答吼器j ；器” 当k = o 时，有彳( 0 ) = 办( ，z 一1 ) ，即一个伪n 边形的所有对角线都可参与剖分，它的剖 分数是办( 疗一1 ) ； 当刀一3 尼( n - _ 3 ) - ( n 一- 4 ) 时，有1 4n 4 n n a , l = o 由于一个凸，z 边形的三角剖 分中至多有，2 3 条对角线，而一个伪行边形的最小伪三角剖分中至多有鱼二娑尘竺条 受限对角线：其中任意疗一3 条对角线不能同时出现在同一个凸，z 边形的三角剖分中，因 此当拓玎一3 时有 a , na 2n n4 l = o 成立则当心一3 4 ，”是偶数 2 0 伪三角剖分性质的研究 m 2 r 卜3 1 2 5 6 图4 3 一个伪刀边形伽为偶数，k = - n 2 ) f i g 4 3ap s e u d on - g o n ( ni sa l le v e nn u m b e r , k - = - n 2 ) r 卜1 隆2 图4 4 一个伪，z 边形为奇数，x = - l - 2 j ) f 培4 4ap s e u d on - g o n ( ni sa no d dn u m b e r ，| ：b