罗炯兴， 王华桥

（1.西昌学院少数民族预科教育学院，四川西昌615013； 2.重庆大学数学与统计学院，重庆401331）

1 预备知识

先给出几个定义.二元k次多项式空间表示为

定义1.1设Ω⊂R2是平面R2上单连通闭区域，而为一个开三角形集，且满足：

3）若任意一个三角形的顶点均不在其他三角形边的内部，则称为Ω上的一个正规三角剖分，记为△，每一个三角形称为三角剖分△的胞腔.

这里强调一点：若无特别说明，全文三角剖分总是指定义1.1的正规三角剖分.

定义 1.2［1］如果在三角形 T：＝〈v1，v2，v3〉内任取一点v0，分别与点v1、v2和v3相连，称为对三角形T进行HCT加密，记为THCT.对三角剖分△每一个三角形胞腔进行HCT加密，称为对三角剖分△进行HCT加密.

定义1.3对于给定的整数k和r，满足0≤r≤k-1，称，对所有T∈△｝为三角剖分△上的二元k次r阶光滑样条函数空间，记为.

本文中总以｜P｜表示任意集合P的基数.

以△表示单连通闭区域Ω⊂R2的正规三角剖分，其中三角形的顶点和边分别称为三角剖分△的网点和网线，位于边界的网点和网线分别称为三角剖分△的边界网点和边界网线，其余的网点和网线分别称为三角剖分△的内网点和内网线.在三角剖分△中，与网点相连网线的数目称为网点的度数，引入如下记号：N表示三角形胞腔的集合、V（E）表示网点（网线）的集合、EI表示内网线的集合、EB表示边界网线的集合、VI表示内网点的集合、VB表示边界网点的集合、V3表示度数为3的内网点的集合.显然

根据图论中的欧拉公式有下列关系成立：

二元样条函数在数值逼近、曲面拟合、散乱数据插值、多元数值积分、有限元方法、偏微分方程数值解、计算机辅助设计和计算机图形学等方面有着广泛的应用.二元样条函数空间通常是指具有一定整体光滑度的分片多项式样条函数空间，由线性代数的知识可知，实际上样条函数空间是一个线性向量空间.显然，要了解样条函数空间并应用于实际，首要问题是弄清它的代数结构，即确定其维数和基底.

关于二元样条函数空间的代数结构问题，最早始于 Strang［2］给出的关于维数的一个猜想，后来Morgan等［3］证实了这一猜想在次数d≥5和光滑度 r＝1 对任意三角剖分成立.Schumaker［4］讨论了一般正规三角剖分下空间（△）的维数问题，对只含有一个内网点的三角剖分△给出了（△），d≥r＋1的维数公式，并获得了任意三角剖分△下空间（△）的维数著名下界公式，被学者广为引用.Alfeld 等［5］和王仁宏等［6］分别利用 B 网方法和光滑余因子法证明了d≥4r＋1时空间（△）的维数正好达到 Schumaker［4］给出的维数下界.Hong［7］将上述结果改进到d≥3r＋2的情形，它是目前关于一般三角剖分情形下二元样条函数空间维数的最好的结果.Alfeld等［8］进一步得到了当d＝3r＋1不含奇异边的三角剖分△（非退化三角剖分）下空间（△）的维数公式.Alfeld 等［9］利用 B 网方法结合图论的知识将Morgan等［3］关于任意三角剖分下的（△）（d≥5）的维数结果推广到d＝4的情形，不仅给出了空间（△）的维数，而且构造了该空间一组具有局部支集的基函数.

本文依照一定的规则（如算法4.1所示），对平面R2上单连通闭区域Ω⊂R2的任意三角剖分△中个数不超过内网点个数的三角形胞腔进行HCT加密，形成新三角剖分△*，以这种方式产生的新三角剖分△*称为对原三角剖分△进行局部HCT加密，这样原三角剖分△中被加密三角形胞腔将产生3个子三角形.利用B网方法通过递推的方式构造了样条空间（△*）的一个最小决定集，显示了其维数 dim（△*）满足 Schumaker［4］的维数下界公式（6）.

2 二元样条函数的B网方法

记三角形 T：＝〈v1，v2，v3〉，其中 v1（x1，y1）、v2（x2，y2）和 v3（x3，y3）是三角形 T 的3 个顶点，并将顶点以逆时针方向进行排列.

引理 2.1［23］对于任意点 v：＝（x，y）∈R2，与三角形T的3个顶点将会有唯一的表达形式

其中，b1＋b2＋b3＝1，b1、b2和 b3称为点 v关于三角形T的重心坐标，并且对于三角形T，对任意v∈R2，设点v关于三角形T的重心坐标是（b1，b2，b3）.对非负整数 i、j、k，且 i＋j＋k＝d，则关于v的d次Bernstein多项式定义为

且具有下列性质：

由性质3）可知，任一d次多项式p（v）可唯一表示成

其中｛cijk，i＋j＋k＝d｝称为多项式 p（v）关于三角形T的B网系数.

定义与三角形T相对应的区域点的集合

则cijk与ξijk之间形成了一一对应关系，每个三角形T恰好有个区域点，区域点 ξijk对应的 B网系数为 cijk.在三角形 T＝〈v1，v2，v3〉区域点中，规定：

满足｛ξd-i，j，i-j｜0≤j≤i｝的区域点称为与顶点v1距离为i的区域点；

满足｛ξd-i-j，j，i｜0≤j≤d-i｝的区域点称为与边v1v2距离为i的区域点；

圆环 Ri，T（v1）表示与 v1距离为 i的区域点集合；

引理 2.2［23］假设 T：＝〈v1，v2，v3〉和＝〈v4，v3，v2〉是 2 个三角形，它们的公共边为 e：＝〈v2，v3〉.设

对所有 v∈e，n＝0，1，2，…，r，当且仅当

其中，j＋k＝d-n，n＝0，1，2，…，r.

对于三角剖分△，记其区域点的集合为Dd，△：＝.利用 B 网方法研究样条函数空间的一个重要技巧是最小决定集技术，对于任意ξ∈Dd，△，.定义泛函 λξ为 λξs：＝s相应于区域点 ξ的B网系数.

定义 2.3［5］对于任意 s∈（△），若区域点集 P⊆Dd，△，满足 λξs＝0，对任意 ξ∈P⇒s≡0，则称P为空间（△）的一个决定集（determining set）.如果空间（△）中不存在基数小于｜P｜的决定集，则称P为空间（△）的一个最小决定集（minimal determining set，简称 MDS）.空间（△）中的最小决定集具有如下2个性质：

显然样条函数Bξ构成了空间（△）的一组基［24］，通常称｛λξ｝ξ∈P为相对于最小决定集P的对偶基.

引理 2.4［5］如果 P⊆Dd，△为空间（△）的一个决定集，则 dim（△）≤｜P｜.

3 相关引理

Schumaker［4］于1979年给出了关于任意三角剖分△下空间（△）的维数下界公式，此维数下界公式是目前能够确定其维数的空间（△）（d≥2r＋1）的精确维数公式，如下列引理所示：

引理 3.1［4］对于任意三角剖分△，空间（△）的维数满足

其中，｜EI｜和｜VI｜分别表示三角剖分△的内网线集合和内网点总数表示与第i个内网点相连的不同斜率的内网线的数目，.

若内网点是2条直线段的交点，则称该内网点为奇异网点，记VS表示三角剖分△中奇异网点的集合.如果 v是三角剖分△的一个内网点，设e（v）、~（v）分别表示与内网点v相连的内网线和斜率不相等的内网线的条数，显然由三角剖分的定义可知，e（v）≥3，~（v）≥2.若 v 是奇异网点，则e（v）＝4，~（v）＝2.对于空间（△），仅在奇异网点处，σi＝1，其余 σi＝0（i＝1，2，…，｜VI｜），即根据欧拉公式

由引理3.1得

为了讨论问题的方便，现在引入广义星型区域的定义.广义星型区域是对一般意义的星型区域按一定的方式增加一些网点和网线而形成的特殊三角剖分，这里星型区域是指所有的三角形胞腔共享一个内网点（如图1（a）所示）.

定义3.2对星型区域Star（v）一部分或全部三角形胞腔进行HCT加密而形成的新三角剖分，称之为广义星型区域（如图1（b）所示），记为 GStar（v）.

图1 广义星型区域GStar（v）Fig.1 The generalized star region GStar（v）

由图1可知，星型区域只有一个内网点v，与之相对应的广义星型区域不止一个内网点，但除内网点v之外的其余内网点都与内网点v相连.星型区域Star（v）可以认为是广义星型区域 GStar（v）的特殊情形.另外，对星型区域Star（v）中全部三角形胞腔进行HCT加密形成的广义星型区域就是对星型区域Star（v）进行HCT加密.下面用B网方法构造广义星型区域 GStar（v）下空间（GStar（v））的最小决定集，进而确定其维数.

引理 3.3［25］如图2，在三角形 T：＝〈v1，v2，v3〉内任取一点vT，三角形T的顶点按逆时针进行标号，记THCT中的3 个子三角形为Tm：＝〈vT，vm，vm＋1〉（m＝1，2，3），这里 v3＋1＝v1.若圆盘 D1，THCT（vm）（m＝1，2，3）中的区域点对应的B网系数为零，且三角形 Tm（m＝1，2，3）任意2个三角形中心对应的区域点和区域点 vT对应的 B网系数为零.若 s∈（THCT），则区域点D3，THCT中所有区域点对应的 B网系数为零.

图2 （T HCT）的最小决定集（由区域点●组成）Fig.2 The minimal determining set of（T HCT）（consisting of the region points●）

在图2中，区域点●对应的B网系数为零，根据引理2.2中的B网方法光滑条件（5）式可知，区域点○对应的B网系数被迫使为零.

引理 3.4记 VB、VI分别表示 GStar（v）的边界和内网点集合，则有

其中，｜VI｜≤｜VB｜＋1.当且仅当点 v为奇异内网点时，σ＝1，否则 σ＝0.

证明将分情形予以证明.

情形2 对Star（v）中全部三角形胞腔进行HCT 加密（如图3（a）所示）.在文献［25］中已有相应的最小决定集的构造方法，现在给出最小决定集的另一种构造方法.记三角形 Ti：＝〈v，vi，vi＋1〉（i＝1，2，…，n），这里 vn＋1＝v1.对三角形 Ti进行HCT加密时在三角形内部取出的点记为vTi.下面D3，GStar（v）中的区域点构成集合 P：

1）选取与网点 v相连的某一个三角形内D1，GStar（v）（v）的 3 个区域点；

2）选取与网点 vi相连的某一个三角形内D1，GStar（v）（vi）（i＝1，2，…，n）的 3 个区域点；

3）选取与网线〈vi，v〉（i＝1，2，…，n）相邻的某一个三角形内中心的一个区域点；

4）选取网点 vTi（i＝1，2，…，n）对应的一个区域点.

情形3 对Star（v）中一部分三角形胞腔进行HCT加密（如图3（b）所示）.不失一般性，不妨设三角形 T1：＝〈v，v1，v2〉没有进行 HCT 加密.若三角形 Ti：＝〈v，vi，vi＋1〉已经进行 HCT 加密，对位于三角形 Ti内部的一网点设为 vTi，这里 i∈｛1，2，…，n｝，vn＋1＝v1.下面D3，GStar（v）中的区域点构成集合P：

1）选取与网点 v相连的某一个三角形内D1，GStar（v）（v）的3 个区域点和三角形 T1中心对应的一个区域点；

2）选取与网点 vi相连的某一个三角形内D1，GStar（v）（vi）（i＝1，2，…，n）的 3 个区域点；

3）选取进行 HCT加密的三角形 Ti中网点vTi（i∈｛2，3…，n｝）对应的一个区域点；

4）若三角形 Ti（i∈｛2，3…，n-1｝）已经进行HCT 加密，选取与网线〈v，vi＋1〉相邻的某一个三角形内中心的一个区域点，

5）若三角形Tn没有进行HCT加密，将会对2）在空间 D1，GStar（v）（v1）选取的 3 个区域点中去掉一个位于网线〈v，v1〉内部的一个区域点.

图3 （GStar（v））的最小决定集（由区域点●组成）Fig.3 The minimal determining set of（GStar（v））（consisting of the region points●）

现在介绍关于三角剖分扩充［26］的瓣（Flap）、对（Pair）和填充（Fill）的概念.

瓣：由原三角剖分的一条边界网线和剖分外一个网点构成的一个三角形.

对：由原三角剖分的2条相邻的边界网线和剖分外一个网点构成的2个三角形.

填充：由原三角剖分的2条相邻的边界网线构成的一个三角形.

显然，任意三角剖分△都可以从一个三角形经过瓣、对和填充的3种扩张而得到.在空间S13（△）中，描述一种特殊对，称之为非理想对，如下述所示：

非理想对：由原三角剖分的2条共线的相邻边界网线和剖分外一个网点构成的2个三角形，并且满足在原三角剖分中这2条相邻边界网线相交的边界网点，不是新形成的三角剖分的奇异内网点.

引理3.5设在三角剖分△下空间S13（△）的最小决定集是P，并且P的基数｜P｜等于Schumak-er［4］维数下界.

1）对三角剖分△增加一个填充，并对填充的三角形T进行HCT加密，记进行HCT加密时在三角形T内取的点为vT，其对应的一个区域点组成的集合记为Q，这样形成新三角剖分记为△′，则P∪Q是新三角剖分△′下空间（△′）的最小决定集.

2）对三角剖分△增加一个非理想对，并对非理想对其中一个三角形T进行HCT加密，记进行HCT加密时在三角形T内取的点为vT，这样形成新三角剖分记为△′，则可以在新三角剖分△′的区域点中选取不属于三角剖分△的4个区域点组成集合，记为Q，使P∪Q成为新三角剖分△′下空间（△′）的最小决定集.

证明1）把填充的三角形T的顶点按逆时针进行标号，记为 v1、v2、v3（如图4（a）所示）.记 Tm：＝〈vT，vm，vm＋1〉（m＝1，2，3）.把对三角形 T 进行HCT加密后记为THCT，由条件得在三角剖分△上的区域点对应的B网系数为零，由引理2.2可知：圆盘 D1，THCT（vm）（m＝1，2，3），以及三角形 T1：＝〈vT，v1，v2〉和 T3：＝〈vT，v3，v1〉中心的区域点对应的B网系数为零.由引理3.3知P∪Q是新三角剖分△′下的空间（△′）的决定集，于是有

图4 集合Q（由区域点●组成）Fig.4 The sets Q （consisting of the region points●）

从三角剖分△到三角剖分△′过程中，将三角剖分△中的一个边界网点变成非奇异内网点v1和新增加了一个非奇异内网点 vT.设分别是三角剖分△（△′）的边界网点、内网点和奇异内网点，则有｜VS｜.由假设1，又由（7）式有

2）把增加的非理想对的2个三角形的顶点按逆时针进行标号，记为 v1、v2、v3、v4（如图4（b）所示）.记三角形 T1：＝〈vT，v1，v2〉，T2：＝〈vT，v2，v4〉，T3：＝〈v2，v3，v4〉，T4：＝〈vT，v4，v1〉，由引理 2.2 可知：D1，△′（v1）∩（T1∪T4）、D1，△′（v2）∩（T1∪T2∪T3）、D1，△′（v3）∩T3的区域点对应的 B 网系数为零，三角形T1、T3中心的区域点对应的B网系数为零.设点 vT对应的一个区域点和 D1，△′（v4）∩T3中的3 个区域点对应的B网系数为零，记这4个区域点所组成的集合记为Q，进而由二元三次样条函数在边〈v2，v4〉一阶光滑使三角形T1中心区域点对应的B网系数为零.由引理3.3 知，在三角形 T1、T2、T4中剩余的区域点对应的B网系数也为零.所以，P∪Q是新三角剖分△′下的空间（△′）的决定集，于是有

从三角剖分△到三角剖分△′过程中，将三角剖分△中的一个边界网点变成非奇异内网点v2和新增加了一个边界网点v4和一个非奇异内网点vT.设VB、分别是三角剖分△（△′）的边界网点、内网点和奇异内网点，则由假设2｜VI｜＋ ｜VS｜＋1，又由（7）式有

4 三角剖分的局部HCT加密与二元样条空间（△*）的维数

对平面R2上单连通闭区域Ω的任意三角剖分△，按照一定的规则对个数不超过内网点个数的三角形胞腔进行HCT加密而得到的一个新的三角剖分，称为对三角剖分△的局部加密，记为△*.并利用递推的方法构造了二元样条空间（△*）一个最小决定集，进而确定了空间（△*）的维数，显示了其维数 dim（△*）等于 Schumaker［4］的维数下界.

对任意三角剖分△进行局部加密所依据的规则，以算法的形式表现.为了算法描述得比较简洁，引入符号V（△）表示三角剖分△中网点的集合，以及

其中，f∈N＋且 f≥2，V（GStarf（v））＼V（GStarf-1（v））表示在 V（GStarf（v））中除去含 V（GStarf-1（v））的网点剩余网点组成的集合.另外，类似定义符号Starf（v），并称之为 f层星型区域.

事实上，符号GStarf（v）的定义等价于对通常意义下f层星型区域Starf（v），就是对一部分或全部的三角形胞腔进行HCT加密后所形成的一种三角剖分，并称之为f层广义星型区域.这样的断言是基于正规三角剖分△的一个事实：度数为3的内网点必位于三角剖分△中一个三角形的内部.这里不采用这样等价定义，而用（9）式来定义GStarf（v），是为了便于对三角剖分△的局部加密过程更好地描述.

下面给出对三角剖分△进行局部加密算法.

算法4.1（三角剖分的局部加密）对三角剖分进行适当的矫正，若存在贯穿于三角剖分△的一条内网线，但不是三角剖分△中的瓣的一条边，则与之相邻的网点是边界网点，记为B1、B2.在此条内网线内部任取一点，与此内网线相邻的2个三角形中异于B1、B2的一个顶点相连，逐一进行矫正后，将形成的三角剖分仍记为三角剖分△.

此算法是从三角剖分△中的一个广义星型区域开始，按照下列规则来对三角剖分△进行局部加密，可能会对个数不超过内网点个数的三角形胞腔进行HCT加密.

1）在三角剖分△中选取与边界网点相邻的一个内网点v，且e（v）≠3，考虑点v的广义星型区域GStar1（v）.

2）记广义星型区域GStar1（v）中的边界网点，且是原三角剖分△中的内网点组成的集合为（不失一般性，按逆时针方向排序）.事实上，网点集及其在三角剖分△中相邻两网点之间的网线形成了一系列折线.

和它们在三角剖分△中相邻之间的网线形成的三角剖分，其中 k＝0，1，…，N.规定 VJ（u0）＝∅，显然GST△（u0）＝GStar1（v），GST△（uk）是三角剖分△中的一部分.记符号VJ（uk）表示与点uk相邻的属于三角剖分△但不属于GST△（uk-1）的网点组成的集合，其中k＝1，2，…，N.记 wk-1、wk＋1表示 GST△（uk-1）中与网点uk相邻的2个边界网点.不失一般性，规定∠wk-1ukwk＋1的角平分线右边的网点为wk-1，左边的网点为 wk＋1.事实上，当 k＝2，3，…，N 时，若网点 uk-1或 uk＋1与 uk相邻，则 wk-1＝uk-1或 wk＋1＝uk＋1，否则 wk-1≠uk-1或 wk＋1≠uk＋1.易知，若网点uk-1或 uk＋1与 uk不相邻，wk-1或 wk＋1必是三角剖分△中的边界网点.

4）在三角剖分中，网点 wk-1、uk、wk＋1是GST△（uk-1）的边界网点，其中 k＝1，2，…，N.设θ＝∠wk-1ukwk＋1，即是在 GST△（uk-1）中与网点uk相连的两条边界网线所成的角.记符号 VBJ（uk）表示 VJ（uk）中属于 GST△（uk）的边界网点组成的集合，其 中 k＝1，2，…，N.一 般 地，｜VBJ（uk）｜≤｜VJ（uk）｜，对于｜VBJ（uk）｜＝｜VJ（uk）｜的情形，现在分 3种类型予以考虑：

（a）若 θ＜ π，VBJ（uk）＝∅.显然这是在原三角剖分GST△（uk-1）上添加了一个填充，对三角形T：＝〈wk-1，uk，wk＋1〉进行 HCT 加密，即对填充进行HCT加密.

（b）若 θ＝π，｜VBJ（uk）｜＝1，且满足网点 uk不是三角剖分 GST△（uk）的奇异内网点.显然这是在GST△（uk-1）上添加了一个非理想对时，对这个非理想对中的2个三角形中的某一个三角形进行HCT加密.

（c）若 θ＞ π，｜VBJ（uk）｜＝2，且网点 uk不是三角剖分GST△（uk）的奇异内网点.按逆时针方向标记VBJ（uk）中的 2 个网点分别为 wJ1、wJ2.还满足网点wk-1、uk、wJ2共线，和网点 wk＋1、uk、wJ1共线，这时，对三角形 T1：＝〈wk-1，uk，wJ1〉，T2：＝〈wJ1，uk，wJ2〉，T3：＝〈wJ2，uk，wk＋1〉中某一个三角形进行HCT加密.

这样就对GStar1（v）的边界网点，且是三角剖分△内网点考虑完毕.

5）将 GStar2（v）替代算法 4.1 中 1）的广义星型区域GStar1（v），将2）中的第一句改为“记 2层广义星型区域GStar2（v）中的边界网点，且是原三角剖分△中的内网点组成的集合为（按逆时针方向排序）”.按照同样的过程类比重复算法2）、3）、4）来进行循环，依次类推，如果在算法 2）中的时，终止算法.

显然，此算法不会对三角剖分△的瓣进行HCT加密.平面R2上单连通闭区域Ω⊂R2的任意三角剖分△，算法4.1在经过有限次循环后必然会终止，故此算法在实际操作中是可行的.根据算法4.1将会在内网点V3处，不会产生有需要进行HCT加密的三角形胞腔，故对三角剖分△进行局部加密时，至多只对（｜VI｜- ｜V3｜）个三角形胞腔进行 HCT加密.甚至在最理想的情况下，将会没有一个三角形胞腔进行HCT加密，不会对三角剖分△进行局部加密.总之，对三角剖分△应用算法4.1，形成的新三角剖分中网点的个数不会大幅增加.例如三角剖分△的CT加密三角剖分△CT，对其应用算法4.1不会产生有需要进行HCT加密的三角形胞腔，可见执行算法4.1不会对CT加密三角剖分△CT进行局部加密.另外，在注记2中给出了对算法4.1灵活运用的2种变形.

图5显示了对三角剖分△进行局部加密的一个图例，是从图中三角剖分中的内网点vstant开始进行算法4.1，算法仅仅循环2次，在图5中进行局部加密时新增的网线用黑色粗实线标出，只需对3个三角形胞腔进行HCT加密.由（7）式知样条函数空间（△）的维数下界只与三角剖分的网点有关，可见执行算法4.1对三角剖分△进行局部加密后不会使样条函数空间（△）的维数大幅度增加.

图5 （△*）的最小决定集（由区域点●组成）Fig.5 The minimal determining set of（△*）（consisting of the region points●）

定理4.2对于单连通闭区域Ω⊂R2上任意三角剖分△，应用算法4.1进行局部加密，将局部加密后的三角剖分记为△*，在三角剖分△*上空间（△*）的维数具有非奇异性，且等于 Schu-maker［4］的维数下界

证明为了证明此结论，应用算法4.1对三角剖分△局部加密的过程，逐步构造空间（△*）的一个最小决定集.

证明过程中将会利用算法4.1在每次循环过程中由2）产生的三角剖分△中的内网点集（按 逆 时 针 方 向 排 列 ），将 内 网 点 集中的点分为 4 种类型：

类型 1 如算法4.1中第4）步（a）描述的情形；

类型 2 如算法4.1中第4）步（b）描述的情形；

类型 3 如算法4.1中第4）步（c）描述的情形；

类型4 除了类型1、类型2和类型3的情形.

首先对算法4.1的1）中进入算法循环的广义星型区域 GStari（v），假定已取出样条空间（GStari（v））的最小决定集，且基数符合定理的结论，其中 i＝1，2，…，GStari（v）＝GST△（u0）.

在算法4.1进行过程中，取属于 GST△（uk）但不属于GST△（uk-1）的一些区域点组成的集合Q，使与样条空间（GST△（uk-1））的最小决定集 P的并集P∪Q成为样条空间（GST△（uk））的最小决定集，这里P∩Q＝∅.对于类型1和类型2的网点uk，集合Q的取法按照引理3.5的1）和2）证明过程，如图4（a）和（b）所示，

对于类型3和类型4的网点uk，一些区域点组成的集合Q的取法如下所示.

类型3的网点uk，相应的网点记法如算法4.1中4）的（c）所标记，区域点集合Q的取法为：

1）取网点vT对应的一个区域点；

2）在与网点wJ1相连的任意的一个三角形中取出在圆盘D1（wJ1）中的3个区域点；

3）在与网点wJ2相连的任意的一个三角形中取出在圆盘D1（wJ2）中的3个区域点.

针对类型3的网点uk的情形取出的区域点集合 Q，不失一般性，设对三角形 T0：＝〈uk，wk-1，wJ1〉进行HCT加密时，在三角形T0内部增加的网点为 vT（如图6（a）所示），类似于引理 3.5 中 2）的证明过程，可以证明区域点集合Q与集合P的并集P∪Q组成三角剖分 GST△（uk）下空间（GST△（uk））的最小决定集（MDS）.

类型 4 的网点 uk，令 Nuk＝｜VBJ（uk）｜，按逆时针方向标记 VBJ（uk）中的网点 v1，v2，…，vNuk，此时区域点集合Q的取法为：

（i）若Nuk＝0.根据对三角剖分△的内网点集分类可知｜VJ（uk）｜＝1 和 ｜VBJ（uk）｜＝0，此时三角形〈wk＋1，uk，wk-1〉已经形成了 HCT 加密，取出三角形〈wk＋1，uk，wk-1〉内部网点对应的一个区域点.

（ii）若 Nuk＝1，且｜VBJ（uk）｜＝｜VJ（uk）｜.

（a）如果网点 wk＋1、uk、wk-1共线，根据对算法4.1中类型4的分类得网点uk是三角剖分的奇异内网点（如图6（b）所示）.此时，在三角形〈v1，uk，wk＋1〉中取出圆盘 D1（v1）中的 3 个区域点；

（b）如果网点 wk＋1、uk、wk-1不共线，此时在三角形〈v1，uk，wk＋1〉中取出圆盘 D1（v1）中的网线〈v1，wk＋1〉上的 2 个区域点.

（iii）若 Nuk＝1，｜VBJ（uk）｜＜ ｜VJ（uk）｜，或者 Nuk≥2.

（a）如果 Nuk＝1，且｜VBJ（uk）｜＜ ｜VJ（uk）｜.这里2个三角形 T1：＝〈wk-1，uk，v1〉和 T2：＝〈v1，uk，wk＋1〉中至少有一个已经被HCT加密，此时取出与点v1相连的某一个三角形中圆盘D1（v1）中的3个区域点.当三角形T1和T2都已经被进行了HCT加密时，然后再取2个三角形T1和T2内部的内网点对应的2个区域点和与网线〈v1，uk〉相邻的某一个三角形中心的一个区域点；当三角形T1和T2只有一个已经被进行了HCT加密时，不失一般性，不妨设三角形T1已经被HCT加密，然后再取出三角形T1内部的内网点对应的一个区域点.

（b）如果 Nuk≥2，且 ｜VBJ（uk）｜＝｜VJ（uk）｜（如图6（c）所示），此时区域点的取法如下：

1）在三角形〈uk，wk-1，v1〉中取出在圆盘D1（v1）中的3 个区域点；

2）在三角形〈uk，vi，vi＋1〉（i＝1，2，…，Nuk-1）中取出在圆盘D1（vi＋1）中的 3 个区域点；

3）在 三 角 形 〈ukvNuk，wk＋1〉中 取 出 圆 盘D1（vNuk）∩〈vNuk，wk＋1〉中的 2 个区域点.

（c）Nuk≥2，且｜VBJ（uk）｜＜ ｜VJ（uk）｜（如图6（d）所示）.假如对三角形T0：＝〈uk，wk-1，v1〉已经进

图6 集合Q（由区域点●组成）Fig.6 The sets Q （consisting of the region points●）

行HCT加密，记三角形T1内的网点为hv0，假如对三角形 Ti：＝〈uk，vi，vi＋1〉（i＝1，2，…，Nuk-1）已经进行HCT加密.记三角形Ti内的网点为hvi，假如对三角形 TNuk：＝〈uk，vNuk，wk＋1〉已经进行 HCT加密，记三角形TNuk内部的网点为hvNuk.此时，区域点的取法如下：

1）在与网点 vi（i＝1，2，…，Nuk）相连的某一个三角形中取出在圆盘D1（vi）中的3个区域点.

2）对于三角形 Ti（i＝0，1，2，…，Nuk-2），若进行了 HCT 加密，取与网线〈uk，vi＋1〉相邻的某一个三角形中心的一个区域点和网点hvi对应的一个区域点.

3）若三角形TNuk-1已经进行HCT加密.如果三角形TNuk没有进行HCT加密，取网点hvNuk-1对应的一个区域点；如果三角形TNuk进行了HCT加密，取与网线〈uk，vNuk〉相邻的某一个三角形中心的点和网点hvNuk-1对应的2个区域点.若三角形TNuk-1没有进行HCT加密，且三角形TNuk也没有进行HCT加密，则1）中取出的圆盘D1（vNuk）中去掉在网线〈uk，vNuk〉内部的一个区域点.

4）对于三角形TNuk，若进行了HCT加密，取网点hvNuk对应的一个区域点.

针对类型4的点uk的情形取出的区域点集合Q，根据光滑性条件引理 2.2、3.3、3.4 和维数下界公式（7），可以证明区域点集合Q与集合P的并集P∪Q是三角剖分GST△（uk）下二元样条函数空间S13（GST△（uk））的最小决定集.

这样，随着算法4.1的循环结束，已经在三角剖分△*中f层广义星型区域 GStarf（v）下空间S13（GStarf（v））构造了一个最小决定集，记为 R，其中f是一个正整数.实际上，当算法4.1对三角剖分△进行局部加密形成三角剖分△*时，此过程没有涉及到三角剖分的瓣（Flap）.由于三角剖分△*可以认为是由其瓣（Flap）和 GStarf（v）组成，对于三角剖分△*的每一个瓣，取瓣中与内网线相对的边界网点一阶圆盘中的3个区域点组成集合T.显然，R∩T＝∅，易知R∩T是空间S13（△*）构造的一个决定集.易计算集合R∩T的基数等于Schumaker［4］维数的下界，故 R∩T 是空间 S13（△*）构造的一个最小决定集.

综上所述，定理中的结论成立.

在图5和图6中区域点●对应的B网系数为零，根据引理2.2中的B网方法光滑条件（5）式可知，区域点○对应的B网系数被迫使为零.

对图5所示的三角剖分△应用算法4.1，从三角剖分中的内网点vstant开始对其进行局部HCT加密.图5中的黑色粗实线是应用算法4.1过程中，对三角剖分△局部HCT加密时添加的网线，得到加密后的三角剖分△*的边界网点数内网点数和奇异网点数由定理4.2得三角剖分△*下空间的维数

依照定理4.2的证明过程，构造的最小决定集是由图5中的黑色实心圆点●的区域点组成.

5 注记

注记1在算法4.1的1）中考虑的内网点v，要求与边界网点相连，可以推广到三角剖分△中任意一个内网点，不受与边界网点相邻的限制.另外，对度数为3的内网点v，即e（v）＝3，视为一种特殊网点不予以考虑的理由，是基于正规三角剖分△中这样一个事实：度数为3的内网点必位于三角剖分△中一个三角形的内部，即度数为3的内网点v及其相邻的3条内网线必视为对三角剖分△中一个三角形进行了HCT加密.根据正规三角剖分的构造可得，算法4.1 的2）中内网点集满足

即内网点 uk的度数不等于3，其中k＝1，2，…，N.

注记2王伟等［27］提出了对三角剖分△的内网点进行排序的概念，若在应用算法4.1过程中考虑星型区域Star（v）（即所有三角形共享于一个顶点v）和n层星型区域Starn（v）来替代广义星型区域GStar（v）和 GStarn（v）去执行算法，此时对三角剖分进行的局部加密，只是进行HCT加密的三角形胞腔可能会增加，但局部加密后的新三角剖分△*下空间（△*）的维数也符合定理4.2的结论.同时，也可以说明在平面上单连通闭区域Ω的三角剖分，如果满足存在内网线是贯穿线，并且是三角剖分的瓣的一条边，则它的内网点是可以排序且满足紧密相连的条件，这样文献［27］关于二元弱样条函数空间的维数结果具有一定的普遍性.

若已经对三角剖分△的内网点进行排序且满足紧密相连的条件，在第一个内网点的星型区域基础上从第二个内网点开始以后的每一个网点执行算法4.1中3）、4）步的方式来对三角剖分△进行局部加密而得到三角剖分△*，在三角剖分△*下空间（△*）维数也符合定理4.2的结论.使用文献［27］中排序方式对I、II型三角剖分的内顶点标号，对文献［28-29］定义的广义 I、II型三角剖分（如图7（a）和（b）所示）依这样的顺序应用算法4.1将不会有三角形胞腔进行HCT加密，三角剖分将不会进行局部加密，且在广义 I、II型三角剖分的维数也符合定理4.2的结论.

图7 广义I型、II型三角剖分Fig.7 The generalized I-type and II-type triangulation

注记3 应用算法4.1可以构造一些特殊三角剖分，在这些三角剖分△下空间（△）的维数仅仅依靠三角剖分的拓扑性质，与其几何性质无关.图8就是这样的一个例子，从内网点O开始执行算法4.1，不会产生需要进行HCT加密的三角形胞腔，仅仅循环3次便终止算法.另外，此三角剖分既不是文献［12-14］所定义的分层三角剖分（因为不存在一个拟圈，内网点呈分支状分布（图中黑色的实心圆点）），也不是文献［22］中所研究的6度广义非收缩三角剖分（因为存在边界网点度数大于6）.任何与如图8的三角剖分同胚（不改变其拓扑结构简单拉伸和扭转）的三角剖分下的二元样条函数空间（△）的维数具有非奇异性，符合定理4.2的结论.事实上，可以更进一步表明，对于任意星型区域，在部分或全部的三角形胞腔内按照图8的方式添加一些内网线和内网点，形成的新三角剖分下二元三次一阶光滑样条函数空间的维数也具有非奇异性，符合定理4.2的结论.另外，也可以对一些特殊三角剖分（如图9所示，由三角形等位线形成的三角剖分）下的二元三次一阶光滑样条函数空间构造一个最小决定集，进而确定其维数.

图8 一种收缩三角剖分Fig.8 A kind of contraction triangulation

图9 由三角形等位线形成的三角剖分Fig.9 A kind of triangulation formed by the equipotential lines of a triangle

致谢西昌学院校级科研项目（LGLS201808）对本文给予了支持，谨致谢意.