羅炯興， 王華橋

（1.西昌學(xué)院少數(shù)民族預(yù)科教育學(xué)院，四川西昌615013； 2.重慶大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，重慶401331）

1 預(yù)備知識

先給出幾個定義.二元k次多項式空間表示為

定義1.1設(shè)Ω?R2是平面R2上單連通閉區(qū)域，而為一個開三角形集，且滿足：

3）若任意一個三角形的頂點均不在其他三角形邊的內(nèi)部，則稱為Ω上的一個正規(guī)三角剖分，記為△，每一個三角形稱為三角剖分△的胞腔.

這里強調(diào)一點：若無特別說明，全文三角剖分總是指定義1.1的正規(guī)三角剖分.

定義 1.2［1］如果在三角形 T：＝〈v1，v2，v3〉內(nèi)任取一點v0，分別與點v1、v2和v3相連，稱為對三角形T進行HCT加密，記為THCT.對三角剖分△每一個三角形胞腔進行HCT加密，稱為對三角剖分△進行HCT加密.

定義1.3對于給定的整數(shù)k和r，滿足0≤r≤k-1，稱，對所有T∈△｝為三角剖分△上的二元k次r階光滑樣條函數(shù)空間，記為.

本文中總以｜P｜表示任意集合P的基數(shù).

以△表示單連通閉區(qū)域Ω?R2的正規(guī)三角剖分，其中三角形的頂點和邊分別稱為三角剖分△的網(wǎng)點和網(wǎng)線，位于邊界的網(wǎng)點和網(wǎng)線分別稱為三角剖分△的邊界網(wǎng)點和邊界網(wǎng)線，其余的網(wǎng)點和網(wǎng)線分別稱為三角剖分△的內(nèi)網(wǎng)點和內(nèi)網(wǎng)線.在三角剖分△中，與網(wǎng)點相連網(wǎng)線的數(shù)目稱為網(wǎng)點的度數(shù)，引入如下記號：N表示三角形胞腔的集合、V（E）表示網(wǎng)點（網(wǎng)線）的集合、EI表示內(nèi)網(wǎng)線的集合、EB表示邊界網(wǎng)線的集合、VI表示內(nèi)網(wǎng)點的集合、VB表示邊界網(wǎng)點的集合、V3表示度數(shù)為3的內(nèi)網(wǎng)點的集合.顯然

根據(jù)圖論中的歐拉公式有下列關(guān)系成立：

二元樣條函數(shù)在數(shù)值逼近、曲面擬合、散亂數(shù)據(jù)插值、多元數(shù)值積分、有限元方法、偏微分方程數(shù)值解、計算機輔助設(shè)計和計算機圖形學(xué)等方面有著廣泛的應(yīng)用.二元樣條函數(shù)空間通常是指具有一定整體光滑度的分片多項式樣條函數(shù)空間，由線性代數(shù)的知識可知，實際上樣條函數(shù)空間是一個線性向量空間.顯然，要了解樣條函數(shù)空間并應(yīng)用于實際，首要問題是弄清它的代數(shù)結(jié)構(gòu)，即確定其維數(shù)和基底.

關(guān)于二元樣條函數(shù)空間的代數(shù)結(jié)構(gòu)問題，最早始于 Strang［2］給出的關(guān)于維數(shù)的一個猜想，后來Morgan等［3］證實了這一猜想在次數(shù)d≥5和光滑度 r＝1 對任意三角剖分成立.Schumaker［4］討論了一般正規(guī)三角剖分下空間（△）的維數(shù)問題，對只含有一個內(nèi)網(wǎng)點的三角剖分△給出了（△），d≥r＋1的維數(shù)公式，并獲得了任意三角剖分△下空間（△）的維數(shù)著名下界公式，被學(xué)者廣為引用.Alfeld 等［5］和王仁宏等［6］分別利用 B 網(wǎng)方法和光滑余因子法證明了d≥4r＋1時空間（△）的維數(shù)正好達到 Schumaker［4］給出的維數(shù)下界.Hong［7］將上述結(jié)果改進到d≥3r＋2的情形，它是目前關(guān)于一般三角剖分情形下二元樣條函數(shù)空間維數(shù)的最好的結(jié)果.Alfeld等［8］進一步得到了當(dāng)d＝3r＋1不含奇異邊的三角剖分△（非退化三角剖分）下空間（△）的維數(shù)公式.Alfeld 等［9］利用 B 網(wǎng)方法結(jié)合圖論的知識將Morgan等［3］關(guān)于任意三角剖分下的（△）（d≥5）的維數(shù)結(jié)果推廣到d＝4的情形，不僅給出了空間（△）的維數(shù)，而且構(gòu)造了該空間一組具有局部支集的基函數(shù).

本文依照一定的規(guī)則（如算法4.1所示），對平面R2上單連通閉區(qū)域Ω?R2的任意三角剖分△中個數(shù)不超過內(nèi)網(wǎng)點個數(shù)的三角形胞腔進行HCT加密，形成新三角剖分△*，以這種方式產(chǎn)生的新三角剖分△*稱為對原三角剖分△進行局部HCT加密，這樣原三角剖分△中被加密三角形胞腔將產(chǎn)生3個子三角形.利用B網(wǎng)方法通過遞推的方式構(gòu)造了樣條空間（△*）的一個最小決定集，顯示了其維數(shù) dim（△*）滿足 Schumaker［4］的維數(shù)下界公式（6）.

2 二元樣條函數(shù)的B網(wǎng)方法

記三角形 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關(guān)于三角形T的重心坐標(biāo)，并且對于三角形T，對任意v∈R2，設(shè)點v關(guān)于三角形T的重心坐標(biāo)是（b1，b2，b3）.對非負(fù)整數(shù) i、j、k，且 i＋j＋k＝d，則關(guān)于v的d次Bernstein多項式定義為

且具有下列性質(zhì)：

由性質(zhì)3）可知，任一d次多項式p（v）可唯一表示成

其中｛cijk，i＋j＋k＝d｝稱為多項式 p（v）關(guān)于三角形T的B網(wǎng)系數(shù).

定義與三角形T相對應(yīng)的區(qū)域點的集合

則cijk與ξijk之間形成了一一對應(yīng)關(guān)系，每個三角形T恰好有個區(qū)域點，區(qū)域點 ξijk對應(yīng)的 B網(wǎng)系數(shù)為 cijk.在三角形 T＝〈v1，v2，v3〉區(qū)域點中，規(guī)定：

滿足｛ξd-i，j，i-j｜0≤j≤i｝的區(qū)域點稱為與頂點v1距離為i的區(qū)域點；

滿足｛ξd-i-j，j，i｜0≤j≤d-i｝的區(qū)域點稱為與邊v1v2距離為i的區(qū)域點；

圓環(huán) Ri，T（v1）表示與 v1距離為 i的區(qū)域點集合；

引理 2.2［23］假設(shè) T：＝〈v1，v2，v3〉和＝〈v4，v3，v2〉是 2 個三角形，它們的公共邊為 e：＝〈v2，v3〉.設(shè)

對所有 v∈e，n＝0，1，2，…，r，當(dāng)且僅當(dāng)

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

對于三角剖分△，記其區(qū)域點的集合為Dd，△：＝.利用 B 網(wǎng)方法研究樣條函數(shù)空間的一個重要技巧是最小決定集技術(shù)，對于任意ξ∈Dd，△，.定義泛函 λξ為 λξs：＝s相應(yīng)于區(qū)域點 ξ的B網(wǎng)系數(shù).

定義 2.3［5］對于任意 s∈（△），若區(qū)域點集 P?Dd，△，滿足 λξs＝0，對任意 ξ∈P?s≡0，則稱P為空間（△）的一個決定集（determining set）.如果空間（△）中不存在基數(shù)小于｜P｜的決定集，則稱P為空間（△）的一個最小決定集（minimal determining set，簡稱 MDS）.空間（△）中的最小決定集具有如下2個性質(zhì)：

顯然樣條函數(shù)Bξ構(gòu)成了空間（△）的一組基［24］，通常稱｛λξ｝ξ∈P為相對于最小決定集P的對偶基.

引理 2.4［5］如果 P?Dd，△為空間（△）的一個決定集，則 dim（△）≤｜P｜.

3 相關(guān)引理

Schumaker［4］于1979年給出了關(guān)于任意三角剖分△下空間（△）的維數(shù)下界公式，此維數(shù)下界公式是目前能夠確定其維數(shù)的空間（△）（d≥2r＋1）的精確維數(shù)公式，如下列引理所示：

引理 3.1［4］對于任意三角剖分△，空間（△）的維數(shù)滿足

其中，｜EI｜和｜VI｜分別表示三角剖分△的內(nèi)網(wǎng)線集合和內(nèi)網(wǎng)點總數(shù)表示與第i個內(nèi)網(wǎng)點相連的不同斜率的內(nèi)網(wǎng)線的數(shù)目，.

若內(nèi)網(wǎng)點是2條直線段的交點，則稱該內(nèi)網(wǎng)點為奇異網(wǎng)點，記VS表示三角剖分△中奇異網(wǎng)點的集合.如果 v是三角剖分△的一個內(nèi)網(wǎng)點，設(shè)e（v）、~（v）分別表示與內(nèi)網(wǎng)點v相連的內(nèi)網(wǎng)線和斜率不相等的內(nèi)網(wǎng)線的條數(shù)，顯然由三角剖分的定義可知，e（v）≥3，~（v）≥2.若 v 是奇異網(wǎng)點，則e（v）＝4，~（v）＝2.對于空間（△），僅在奇異網(wǎng)點處，σi＝1，其余 σi＝0（i＝1，2，…，｜VI｜），即根據(jù)歐拉公式

由引理3.1得

為了討論問題的方便，現(xiàn)在引入廣義星型區(qū)域的定義.廣義星型區(qū)域是對一般意義的星型區(qū)域按一定的方式增加一些網(wǎng)點和網(wǎng)線而形成的特殊三角剖分，這里星型區(qū)域是指所有的三角形胞腔共享一個內(nèi)網(wǎng)點（如圖1（a）所示）.

定義3.2對星型區(qū)域Star（v）一部分或全部三角形胞腔進行HCT加密而形成的新三角剖分，稱之為廣義星型區(qū)域（如圖1（b）所示），記為 GStar（v）.

圖1 廣義星型區(qū)域GStar（v）Fig.1 The generalized star region GStar（v）

由圖1可知，星型區(qū)域只有一個內(nèi)網(wǎng)點v，與之相對應(yīng)的廣義星型區(qū)域不止一個內(nèi)網(wǎng)點，但除內(nèi)網(wǎng)點v之外的其余內(nèi)網(wǎng)點都與內(nèi)網(wǎng)點v相連.星型區(qū)域Star（v）可以認(rèn)為是廣義星型區(qū)域 GStar（v）的特殊情形.另外，對星型區(qū)域Star（v）中全部三角形胞腔進行HCT加密形成的廣義星型區(qū)域就是對星型區(qū)域Star（v）進行HCT加密.下面用B網(wǎng)方法構(gòu)造廣義星型區(qū)域 GStar（v）下空間（GStar（v））的最小決定集，進而確定其維數(shù).

引理 3.3［25］如圖2，在三角形 T：＝〈v1，v2，v3〉內(nèi)任取一點vT，三角形T的頂點按逆時針進行標(biāo)號，記THCT中的3 個子三角形為Tm：＝〈vT，vm，vm＋1〉（m＝1，2，3），這里 v3＋1＝v1.若圓盤 D1，THCT（vm）（m＝1，2，3）中的區(qū)域點對應(yīng)的B網(wǎng)系數(shù)為零，且三角形 Tm（m＝1，2，3）任意2個三角形中心對應(yīng)的區(qū)域點和區(qū)域點 vT對應(yīng)的 B網(wǎng)系數(shù)為零.若 s∈（THCT），則區(qū)域點D3，THCT中所有區(qū)域點對應(yīng)的 B網(wǎng)系數(shù)為零.

圖2 （T HCT）的最小決定集（由區(qū)域點●組成）Fig.2 The minimal determining set of（T HCT）（consisting of the region points●）

在圖2中，區(qū)域點●對應(yīng)的B網(wǎng)系數(shù)為零，根據(jù)引理2.2中的B網(wǎng)方法光滑條件（5）式可知，區(qū)域點○對應(yīng)的B網(wǎng)系數(shù)被迫使為零.

引理 3.4記 VB、VI分別表示 GStar（v）的邊界和內(nèi)網(wǎng)點集合，則有

其中，｜VI｜≤｜VB｜＋1.當(dāng)且僅當(dāng)點 v為奇異內(nèi)網(wǎng)點時，σ＝1，否則 σ＝0.

證明將分情形予以證明.

情形2 對Star（v）中全部三角形胞腔進行HCT 加密（如圖3（a）所示）.在文獻［25］中已有相應(yīng)的最小決定集的構(gòu)造方法，現(xiàn)在給出最小決定集的另一種構(gòu)造方法.記三角形 Ti：＝〈v，vi，vi＋1〉（i＝1，2，…，n），這里 vn＋1＝v1.對三角形 Ti進行HCT加密時在三角形內(nèi)部取出的點記為vTi.下面D3，GStar（v）中的區(qū)域點構(gòu)成集合 P：

1）選取與網(wǎng)點 v相連的某一個三角形內(nèi)D1，GStar（v）（v）的 3 個區(qū)域點；

2）選取與網(wǎng)點 vi相連的某一個三角形內(nèi)D1，GStar（v）（vi）（i＝1，2，…，n）的 3 個區(qū)域點；

3）選取與網(wǎng)線〈vi，v〉（i＝1，2，…，n）相鄰的某一個三角形內(nèi)中心的一個區(qū)域點；

4）選取網(wǎng)點 vTi（i＝1，2，…，n）對應(yīng)的一個區(qū)域點.

情形3 對Star（v）中一部分三角形胞腔進行HCT加密（如圖3（b）所示）.不失一般性，不妨設(shè)三角形 T1：＝〈v，v1，v2〉沒有進行 HCT 加密.若三角形 Ti：＝〈v，vi，vi＋1〉已經(jīng)進行 HCT 加密，對位于三角形 Ti內(nèi)部的一網(wǎng)點設(shè)為 vTi，這里 i∈｛1，2，…，n｝，vn＋1＝v1.下面D3，GStar（v）中的區(qū)域點構(gòu)成集合P：

1）選取與網(wǎng)點 v相連的某一個三角形內(nèi)D1，GStar（v）（v）的3 個區(qū)域點和三角形 T1中心對應(yīng)的一個區(qū)域點；

2）選取與網(wǎng)點 vi相連的某一個三角形內(nèi)D1，GStar（v）（vi）（i＝1，2，…，n）的 3 個區(qū)域點；

3）選取進行 HCT加密的三角形 Ti中網(wǎng)點vTi（i∈｛2，3…，n｝）對應(yīng)的一個區(qū)域點；

4）若三角形 Ti（i∈｛2，3…，n-1｝）已經(jīng)進行HCT 加密，選取與網(wǎng)線〈v，vi＋1〉相鄰的某一個三角形內(nèi)中心的一個區(qū)域點，

5）若三角形Tn沒有進行HCT加密，將會對2）在空間 D1，GStar（v）（v1）選取的 3 個區(qū)域點中去掉一個位于網(wǎng)線〈v，v1〉內(nèi)部的一個區(qū)域點.

圖3 （GStar（v））的最小決定集（由區(qū)域點●組成）Fig.3 The minimal determining set of（GStar（v））（consisting of the region points●）

現(xiàn)在介紹關(guān)于三角剖分?jǐn)U充［26］的瓣（Flap）、對（Pair）和填充（Fill）的概念.

瓣：由原三角剖分的一條邊界網(wǎng)線和剖分外一個網(wǎng)點構(gòu)成的一個三角形.

對：由原三角剖分的2條相鄰的邊界網(wǎng)線和剖分外一個網(wǎng)點構(gòu)成的2個三角形.

填充：由原三角剖分的2條相鄰的邊界網(wǎng)線構(gòu)成的一個三角形.

顯然，任意三角剖分△都可以從一個三角形經(jīng)過瓣、對和填充的3種擴張而得到.在空間S13（△）中，描述一種特殊對，稱之為非理想對，如下述所示：

非理想對：由原三角剖分的2條共線的相鄰邊界網(wǎng)線和剖分外一個網(wǎng)點構(gòu)成的2個三角形，并且滿足在原三角剖分中這2條相鄰邊界網(wǎng)線相交的邊界網(wǎng)點，不是新形成的三角剖分的奇異內(nèi)網(wǎng)點.

引理3.5設(shè)在三角剖分△下空間S13（△）的最小決定集是P，并且P的基數(shù)｜P｜等于Schumak-er［4］維數(shù)下界.

1）對三角剖分△增加一個填充，并對填充的三角形T進行HCT加密，記進行HCT加密時在三角形T內(nèi)取的點為vT，其對應(yīng)的一個區(qū)域點組成的集合記為Q，這樣形成新三角剖分記為△′，則P∪Q是新三角剖分△′下空間（△′）的最小決定集.

2）對三角剖分△增加一個非理想對，并對非理想對其中一個三角形T進行HCT加密，記進行HCT加密時在三角形T內(nèi)取的點為vT，這樣形成新三角剖分記為△′，則可以在新三角剖分△′的區(qū)域點中選取不屬于三角剖分△的4個區(qū)域點組成集合，記為Q，使P∪Q成為新三角剖分△′下空間（△′）的最小決定集.

證明1）把填充的三角形T的頂點按逆時針進行標(biāo)號，記為 v1、v2、v3（如圖4（a）所示）.記 Tm：＝〈vT，vm，vm＋1〉（m＝1，2，3）.把對三角形 T 進行HCT加密后記為THCT，由條件得在三角剖分△上的區(qū)域點對應(yīng)的B網(wǎng)系數(shù)為零，由引理2.2可知：圓盤 D1，THCT（vm）（m＝1，2，3），以及三角形 T1：＝〈vT，v1，v2〉和 T3：＝〈vT，v3，v1〉中心的區(qū)域點對應(yīng)的B網(wǎng)系數(shù)為零.由引理3.3知P∪Q是新三角剖分△′下的空間（△′）的決定集，于是有

圖4 集合Q（由區(qū)域點●組成）Fig.4 The sets Q （consisting of the region points●）

從三角剖分△到三角剖分△′過程中，將三角剖分△中的一個邊界網(wǎng)點變成非奇異內(nèi)網(wǎng)點v1和新增加了一個非奇異內(nèi)網(wǎng)點 vT.設(shè)分別是三角剖分△（△′）的邊界網(wǎng)點、內(nèi)網(wǎng)點和奇異內(nèi)網(wǎng)點，則有｜VS｜.由假設(shè)1，又由（7）式有

2）把增加的非理想對的2個三角形的頂點按逆時針進行標(biāo)號，記為 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的區(qū)域點對應(yīng)的 B 網(wǎng)系數(shù)為零，三角形T1、T3中心的區(qū)域點對應(yīng)的B網(wǎng)系數(shù)為零.設(shè)點 vT對應(yīng)的一個區(qū)域點和 D1，△′（v4）∩T3中的3 個區(qū)域點對應(yīng)的B網(wǎng)系數(shù)為零，記這4個區(qū)域點所組成的集合記為Q，進而由二元三次樣條函數(shù)在邊〈v2，v4〉一階光滑使三角形T1中心區(qū)域點對應(yīng)的B網(wǎng)系數(shù)為零.由引理3.3 知，在三角形 T1、T2、T4中剩余的區(qū)域點對應(yīng)的B網(wǎng)系數(shù)也為零.所以，P∪Q是新三角剖分△′下的空間（△′）的決定集，于是有

從三角剖分△到三角剖分△′過程中，將三角剖分△中的一個邊界網(wǎng)點變成非奇異內(nèi)網(wǎng)點v2和新增加了一個邊界網(wǎng)點v4和一個非奇異內(nèi)網(wǎng)點vT.設(shè)VB、分別是三角剖分△（△′）的邊界網(wǎng)點、內(nèi)網(wǎng)點和奇異內(nèi)網(wǎng)點，則由假設(shè)2｜VI｜＋ ｜VS｜＋1，又由（7）式有

4 三角剖分的局部HCT加密與二元樣條空間（△*）的維數(shù)

對平面R2上單連通閉區(qū)域Ω的任意三角剖分△，按照一定的規(guī)則對個數(shù)不超過內(nèi)網(wǎng)點個數(shù)的三角形胞腔進行HCT加密而得到的一個新的三角剖分，稱為對三角剖分△的局部加密，記為△*.并利用遞推的方法構(gòu)造了二元樣條空間（△*）一個最小決定集，進而確定了空間（△*）的維數(shù)，顯示了其維數(shù) dim（△*）等于 Schumaker［4］的維數(shù)下界.

對任意三角剖分△進行局部加密所依據(jù)的規(guī)則，以算法的形式表現(xiàn).為了算法描述得比較簡潔，引入符號V（△）表示三角剖分△中網(wǎng)點的集合，以及

其中，f∈N＋且 f≥2，V（GStarf（v））＼V（GStarf-1（v））表示在 V（GStarf（v））中除去含 V（GStarf-1（v））的網(wǎng)點剩余網(wǎng)點組成的集合.另外，類似定義符號Starf（v），并稱之為 f層星型區(qū)域.

事實上，符號GStarf（v）的定義等價于對通常意義下f層星型區(qū)域Starf（v），就是對一部分或全部的三角形胞腔進行HCT加密后所形成的一種三角剖分，并稱之為f層廣義星型區(qū)域.這樣的斷言是基于正規(guī)三角剖分△的一個事實：度數(shù)為3的內(nèi)網(wǎng)點必位于三角剖分△中一個三角形的內(nèi)部.這里不采用這樣等價定義，而用（9）式來定義GStarf（v），是為了便于對三角剖分△的局部加密過程更好地描述.

下面給出對三角剖分△進行局部加密算法.

算法4.1（三角剖分的局部加密）對三角剖分進行適當(dāng)?shù)某C正，若存在貫穿于三角剖分△的一條內(nèi)網(wǎng)線，但不是三角剖分△中的瓣的一條邊，則與之相鄰的網(wǎng)點是邊界網(wǎng)點，記為B1、B2.在此條內(nèi)網(wǎng)線內(nèi)部任取一點，與此內(nèi)網(wǎng)線相鄰的2個三角形中異于B1、B2的一個頂點相連，逐一進行矯正后，將形成的三角剖分仍記為三角剖分△.

此算法是從三角剖分△中的一個廣義星型區(qū)域開始，按照下列規(guī)則來對三角剖分△進行局部加密，可能會對個數(shù)不超過內(nèi)網(wǎng)點個數(shù)的三角形胞腔進行HCT加密.

1）在三角剖分△中選取與邊界網(wǎng)點相鄰的一個內(nèi)網(wǎng)點v，且e（v）≠3，考慮點v的廣義星型區(qū)域GStar1（v）.

2）記廣義星型區(qū)域GStar1（v）中的邊界網(wǎng)點，且是原三角剖分△中的內(nèi)網(wǎng)點組成的集合為（不失一般性，按逆時針方向排序）.事實上，網(wǎng)點集及其在三角剖分△中相鄰兩網(wǎng)點之間的網(wǎng)線形成了一系列折線.

和它們在三角剖分△中相鄰之間的網(wǎng)線形成的三角剖分，其中 k＝0，1，…，N.規(guī)定 VJ（u0）＝?，顯然GST△（u0）＝GStar1（v），GST△（uk）是三角剖分△中的一部分.記符號VJ（uk）表示與點uk相鄰的屬于三角剖分△但不屬于GST△（uk-1）的網(wǎng)點組成的集合，其中k＝1，2，…，N.記 wk-1、wk＋1表示 GST△（uk-1）中與網(wǎng)點uk相鄰的2個邊界網(wǎng)點.不失一般性，規(guī)定∠wk-1ukwk＋1的角平分線右邊的網(wǎng)點為wk-1，左邊的網(wǎng)點為 wk＋1.事實上，當(dāng) k＝2，3，…，N 時，若網(wǎng)點 uk-1或 uk＋1與 uk相鄰，則 wk-1＝uk-1或 wk＋1＝uk＋1，否則 wk-1≠uk-1或 wk＋1≠uk＋1.易知，若網(wǎng)點uk-1或 uk＋1與 uk不相鄰，wk-1或 wk＋1必是三角剖分△中的邊界網(wǎng)點.

4）在三角剖分中，網(wǎng)點 wk-1、uk、wk＋1是GST△（uk-1）的邊界網(wǎng)點，其中 k＝1，2，…，N.設(shè)θ＝∠wk-1ukwk＋1，即是在 GST△（uk-1）中與網(wǎng)點uk相連的兩條邊界網(wǎng)線所成的角.記符號 VBJ（uk）表示 VJ（uk）中屬于 GST△（uk）的邊界網(wǎng)點組成的集合，其 中 k＝1，2，…，N.一 般 地，｜VBJ（uk）｜≤｜VJ（uk）｜，對于｜VBJ（uk）｜＝｜VJ（uk）｜的情形，現(xiàn)在分 3種類型予以考慮：

（a）若 θ＜ π，VBJ（uk）＝?.顯然這是在原三角剖分GST△（uk-1）上添加了一個填充，對三角形T：＝〈wk-1，uk，wk＋1〉進行 HCT 加密，即對填充進行HCT加密.

（b）若 θ＝π，｜VBJ（uk）｜＝1，且滿足網(wǎng)點 uk不是三角剖分 GST△（uk）的奇異內(nèi)網(wǎng)點.顯然這是在GST△（uk-1）上添加了一個非理想對時，對這個非理想對中的2個三角形中的某一個三角形進行HCT加密.

（c）若 θ＞ π，｜VBJ（uk）｜＝2，且網(wǎng)點 uk不是三角剖分GST△（uk）的奇異內(nèi)網(wǎng)點.按逆時針方向標(biāo)記VBJ（uk）中的 2 個網(wǎng)點分別為 wJ1、wJ2.還滿足網(wǎng)點wk-1、uk、wJ2共線，和網(wǎng)點 wk＋1、uk、wJ1共線，這時，對三角形 T1：＝〈wk-1，uk，wJ1〉，T2：＝〈wJ1，uk，wJ2〉，T3：＝〈wJ2，uk，wk＋1〉中某一個三角形進行HCT加密.

這樣就對GStar1（v）的邊界網(wǎng)點，且是三角剖分△內(nèi)網(wǎng)點考慮完畢.

5）將 GStar2（v）替代算法 4.1 中 1）的廣義星型區(qū)域GStar1（v），將2）中的第一句改為“記 2層廣義星型區(qū)域GStar2（v）中的邊界網(wǎng)點，且是原三角剖分△中的內(nèi)網(wǎng)點組成的集合為（按逆時針方向排序）”.按照同樣的過程類比重復(fù)算法2）、3）、4）來進行循環(huán)，依次類推，如果在算法 2）中的時，終止算法.

顯然，此算法不會對三角剖分△的瓣進行HCT加密.平面R2上單連通閉區(qū)域Ω?R2的任意三角剖分△，算法4.1在經(jīng)過有限次循環(huán)后必然會終止，故此算法在實際操作中是可行的.根據(jù)算法4.1將會在內(nèi)網(wǎng)點V3處，不會產(chǎn)生有需要進行HCT加密的三角形胞腔，故對三角剖分△進行局部加密時，至多只對（｜VI｜- ｜V3｜）個三角形胞腔進行 HCT加密.甚至在最理想的情況下，將會沒有一個三角形胞腔進行HCT加密，不會對三角剖分△進行局部加密.總之，對三角剖分△應(yīng)用算法4.1，形成的新三角剖分中網(wǎng)點的個數(shù)不會大幅增加.例如三角剖分△的CT加密三角剖分△CT，對其應(yīng)用算法4.1不會產(chǎn)生有需要進行HCT加密的三角形胞腔，可見執(zhí)行算法4.1不會對CT加密三角剖分△CT進行局部加密.另外，在注記2中給出了對算法4.1靈活運用的2種變形.

圖5顯示了對三角剖分△進行局部加密的一個圖例，是從圖中三角剖分中的內(nèi)網(wǎng)點vstant開始進行算法4.1，算法僅僅循環(huán)2次，在圖5中進行局部加密時新增的網(wǎng)線用黑色粗實線標(biāo)出，只需對3個三角形胞腔進行HCT加密.由（7）式知樣條函數(shù)空間（△）的維數(shù)下界只與三角剖分的網(wǎng)點有關(guān)，可見執(zhí)行算法4.1對三角剖分△進行局部加密后不會使樣條函數(shù)空間（△）的維數(shù)大幅度增加.

圖5 （△*）的最小決定集（由區(qū)域點●組成）Fig.5 The minimal determining set of（△*）（consisting of the region points●）

定理4.2對于單連通閉區(qū)域Ω?R2上任意三角剖分△，應(yīng)用算法4.1進行局部加密，將局部加密后的三角剖分記為△*，在三角剖分△*上空間（△*）的維數(shù)具有非奇異性，且等于 Schu-maker［4］的維數(shù)下界

證明為了證明此結(jié)論，應(yīng)用算法4.1對三角剖分△局部加密的過程，逐步構(gòu)造空間（△*）的一個最小決定集.

證明過程中將會利用算法4.1在每次循環(huán)過程中由2）產(chǎn)生的三角剖分△中的內(nèi)網(wǎng)點集（按 逆 時 針 方 向 排 列 ），將 內(nèi) 網(wǎng) 點 集中的點分為 4 種類型：

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

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

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

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

首先對算法4.1的1）中進入算法循環(huán)的廣義星型區(qū)域 GStari（v），假定已取出樣條空間（GStari（v））的最小決定集，且基數(shù)符合定理的結(jié)論，其中 i＝1，2，…，GStari（v）＝GST△（u0）.

在算法4.1進行過程中，取屬于 GST△（uk）但不屬于GST△（uk-1）的一些區(qū)域點組成的集合Q，使與樣條空間（GST△（uk-1））的最小決定集 P的并集P∪Q成為樣條空間（GST△（uk））的最小決定集，這里P∩Q＝?.對于類型1和類型2的網(wǎng)點uk，集合Q的取法按照引理3.5的1）和2）證明過程，如圖4（a）和（b）所示，

對于類型3和類型4的網(wǎng)點uk，一些區(qū)域點組成的集合Q的取法如下所示.

類型3的網(wǎng)點uk，相應(yīng)的網(wǎng)點記法如算法4.1中4）的（c）所標(biāo)記，區(qū)域點集合Q的取法為：

1）取網(wǎng)點vT對應(yīng)的一個區(qū)域點；

2）在與網(wǎng)點wJ1相連的任意的一個三角形中取出在圓盤D1（wJ1）中的3個區(qū)域點；

3）在與網(wǎng)點wJ2相連的任意的一個三角形中取出在圓盤D1（wJ2）中的3個區(qū)域點.

針對類型3的網(wǎng)點uk的情形取出的區(qū)域點集合 Q，不失一般性，設(shè)對三角形 T0：＝〈uk，wk-1，wJ1〉進行HCT加密時，在三角形T0內(nèi)部增加的網(wǎng)點為 vT（如圖6（a）所示），類似于引理 3.5 中 2）的證明過程，可以證明區(qū)域點集合Q與集合P的并集P∪Q組成三角剖分 GST△（uk）下空間（GST△（uk））的最小決定集（MDS）.

類型 4 的網(wǎng)點 uk，令 Nuk＝｜VBJ（uk）｜，按逆時針方向標(biāo)記 VBJ（uk）中的網(wǎng)點 v1，v2，…，vNuk，此時區(qū)域點集合Q的取法為：

（i）若Nuk＝0.根據(jù)對三角剖分△的內(nèi)網(wǎng)點集分類可知｜VJ（uk）｜＝1 和 ｜VBJ（uk）｜＝0，此時三角形〈wk＋1，uk，wk-1〉已經(jīng)形成了 HCT 加密，取出三角形〈wk＋1，uk，wk-1〉內(nèi)部網(wǎng)點對應(yīng)的一個區(qū)域點.

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

（a）如果網(wǎng)點 wk＋1、uk、wk-1共線，根據(jù)對算法4.1中類型4的分類得網(wǎng)點uk是三角剖分的奇異內(nèi)網(wǎng)點（如圖6（b）所示）.此時，在三角形〈v1，uk，wk＋1〉中取出圓盤 D1（v1）中的 3 個區(qū)域點；

（b）如果網(wǎng)點 wk＋1、uk、wk-1不共線，此時在三角形〈v1，uk，wk＋1〉中取出圓盤 D1（v1）中的網(wǎng)線〈v1，wk＋1〉上的 2 個區(qū)域點.

（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〉中至少有一個已經(jīng)被HCT加密，此時取出與點v1相連的某一個三角形中圓盤D1（v1）中的3個區(qū)域點.當(dāng)三角形T1和T2都已經(jīng)被進行了HCT加密時，然后再取2個三角形T1和T2內(nèi)部的內(nèi)網(wǎng)點對應(yīng)的2個區(qū)域點和與網(wǎng)線〈v1，uk〉相鄰的某一個三角形中心的一個區(qū)域點；當(dāng)三角形T1和T2只有一個已經(jīng)被進行了HCT加密時，不失一般性，不妨設(shè)三角形T1已經(jīng)被HCT加密，然后再取出三角形T1內(nèi)部的內(nèi)網(wǎng)點對應(yīng)的一個區(qū)域點.

（b）如果 Nuk≥2，且 ｜VBJ（uk）｜＝｜VJ（uk）｜（如圖6（c）所示），此時區(qū)域點的取法如下：

1）在三角形〈uk，wk-1，v1〉中取出在圓盤D1（v1）中的3 個區(qū)域點；

2）在三角形〈uk，vi，vi＋1〉（i＝1，2，…，Nuk-1）中取出在圓盤D1（vi＋1）中的 3 個區(qū)域點；

3）在 三 角 形 〈ukvNuk，wk＋1〉中 取 出 圓 盤D1（vNuk）∩〈vNuk，wk＋1〉中的 2 個區(qū)域點.

（c）Nuk≥2，且｜VBJ（uk）｜＜ ｜VJ（uk）｜（如圖6（d）所示）.假如對三角形T0：＝〈uk，wk-1，v1〉已經(jīng)進

圖6 集合Q（由區(qū)域點●組成）Fig.6 The sets Q （consisting of the region points●）

行HCT加密，記三角形T1內(nèi)的網(wǎng)點為hv0，假如對三角形 Ti：＝〈uk，vi，vi＋1〉（i＝1，2，…，Nuk-1）已經(jīng)進行HCT加密.記三角形Ti內(nèi)的網(wǎng)點為hvi，假如對三角形 TNuk：＝〈uk，vNuk，wk＋1〉已經(jīng)進行 HCT加密，記三角形TNuk內(nèi)部的網(wǎng)點為hvNuk.此時，區(qū)域點的取法如下：

1）在與網(wǎng)點 vi（i＝1，2，…，Nuk）相連的某一個三角形中取出在圓盤D1（vi）中的3個區(qū)域點.

2）對于三角形 Ti（i＝0，1，2，…，Nuk-2），若進行了 HCT 加密，取與網(wǎng)線〈uk，vi＋1〉相鄰的某一個三角形中心的一個區(qū)域點和網(wǎng)點hvi對應(yīng)的一個區(qū)域點.

3）若三角形TNuk-1已經(jīng)進行HCT加密.如果三角形TNuk沒有進行HCT加密，取網(wǎng)點hvNuk-1對應(yīng)的一個區(qū)域點；如果三角形TNuk進行了HCT加密，取與網(wǎng)線〈uk，vNuk〉相鄰的某一個三角形中心的點和網(wǎng)點hvNuk-1對應(yīng)的2個區(qū)域點.若三角形TNuk-1沒有進行HCT加密，且三角形TNuk也沒有進行HCT加密，則1）中取出的圓盤D1（vNuk）中去掉在網(wǎng)線〈uk，vNuk〉內(nèi)部的一個區(qū)域點.

4）對于三角形TNuk，若進行了HCT加密，取網(wǎng)點hvNuk對應(yīng)的一個區(qū)域點.

針對類型4的點uk的情形取出的區(qū)域點集合Q，根據(jù)光滑性條件引理 2.2、3.3、3.4 和維數(shù)下界公式（7），可以證明區(qū)域點集合Q與集合P的并集P∪Q是三角剖分GST△（uk）下二元樣條函數(shù)空間S13（GST△（uk））的最小決定集.

這樣，隨著算法4.1的循環(huán)結(jié)束，已經(jīng)在三角剖分△*中f層廣義星型區(qū)域 GStarf（v）下空間S13（GStarf（v））構(gòu)造了一個最小決定集，記為 R，其中f是一個正整數(shù).實際上，當(dāng)算法4.1對三角剖分△進行局部加密形成三角剖分△*時，此過程沒有涉及到三角剖分的瓣（Flap）.由于三角剖分△*可以認(rèn)為是由其瓣（Flap）和 GStarf（v）組成，對于三角剖分△*的每一個瓣，取瓣中與內(nèi)網(wǎng)線相對的邊界網(wǎng)點一階圓盤中的3個區(qū)域點組成集合T.顯然，R∩T＝?，易知R∩T是空間S13（△*）構(gòu)造的一個決定集.易計算集合R∩T的基數(shù)等于Schumaker［4］維數(shù)的下界，故 R∩T 是空間 S13（△*）構(gòu)造的一個最小決定集.

綜上所述，定理中的結(jié)論成立.

在圖5和圖6中區(qū)域點●對應(yīng)的B網(wǎng)系數(shù)為零，根據(jù)引理2.2中的B網(wǎng)方法光滑條件（5）式可知，區(qū)域點○對應(yīng)的B網(wǎng)系數(shù)被迫使為零.

對圖5所示的三角剖分△應(yīng)用算法4.1，從三角剖分中的內(nèi)網(wǎng)點vstant開始對其進行局部HCT加密.圖5中的黑色粗實線是應(yīng)用算法4.1過程中，對三角剖分△局部HCT加密時添加的網(wǎng)線，得到加密后的三角剖分△*的邊界網(wǎng)點數(shù)內(nèi)網(wǎng)點數(shù)和奇異網(wǎng)點數(shù)由定理4.2得三角剖分△*下空間的維數(shù)

依照定理4.2的證明過程，構(gòu)造的最小決定集是由圖5中的黑色實心圓點●的區(qū)域點組成.

5 注記

注記1在算法4.1的1）中考慮的內(nèi)網(wǎng)點v，要求與邊界網(wǎng)點相連，可以推廣到三角剖分△中任意一個內(nèi)網(wǎng)點，不受與邊界網(wǎng)點相鄰的限制.另外，對度數(shù)為3的內(nèi)網(wǎng)點v，即e（v）＝3，視為一種特殊網(wǎng)點不予以考慮的理由，是基于正規(guī)三角剖分△中這樣一個事實：度數(shù)為3的內(nèi)網(wǎng)點必位于三角剖分△中一個三角形的內(nèi)部，即度數(shù)為3的內(nèi)網(wǎng)點v及其相鄰的3條內(nèi)網(wǎng)線必視為對三角剖分△中一個三角形進行了HCT加密.根據(jù)正規(guī)三角剖分的構(gòu)造可得，算法4.1 的2）中內(nèi)網(wǎng)點集滿足

即內(nèi)網(wǎng)點 uk的度數(shù)不等于3，其中k＝1，2，…，N.

注記2王偉等［27］提出了對三角剖分△的內(nèi)網(wǎng)點進行排序的概念，若在應(yīng)用算法4.1過程中考慮星型區(qū)域Star（v）（即所有三角形共享于一個頂點v）和n層星型區(qū)域Starn（v）來替代廣義星型區(qū)域GStar（v）和 GStarn（v）去執(zhí)行算法，此時對三角剖分進行的局部加密，只是進行HCT加密的三角形胞腔可能會增加，但局部加密后的新三角剖分△*下空間（△*）的維數(shù)也符合定理4.2的結(jié)論.同時，也可以說明在平面上單連通閉區(qū)域Ω的三角剖分，如果滿足存在內(nèi)網(wǎng)線是貫穿線，并且是三角剖分的瓣的一條邊，則它的內(nèi)網(wǎng)點是可以排序且滿足緊密相連的條件，這樣文獻［27］關(guān)于二元弱樣條函數(shù)空間的維數(shù)結(jié)果具有一定的普遍性.

若已經(jīng)對三角剖分△的內(nèi)網(wǎng)點進行排序且滿足緊密相連的條件，在第一個內(nèi)網(wǎng)點的星型區(qū)域基礎(chǔ)上從第二個內(nèi)網(wǎng)點開始以后的每一個網(wǎng)點執(zhí)行算法4.1中3）、4）步的方式來對三角剖分△進行局部加密而得到三角剖分△*，在三角剖分△*下空間（△*）維數(shù)也符合定理4.2的結(jié)論.使用文獻［27］中排序方式對I、II型三角剖分的內(nèi)頂點標(biāo)號，對文獻［28-29］定義的廣義 I、II型三角剖分（如圖7（a）和（b）所示）依這樣的順序應(yīng)用算法4.1將不會有三角形胞腔進行HCT加密，三角剖分將不會進行局部加密，且在廣義 I、II型三角剖分的維數(shù)也符合定理4.2的結(jié)論.

圖7 廣義I型、II型三角剖分Fig.7 The generalized I-type and II-type triangulation

注記3 應(yīng)用算法4.1可以構(gòu)造一些特殊三角剖分，在這些三角剖分△下空間（△）的維數(shù)僅僅依靠三角剖分的拓?fù)湫再|(zhì)，與其幾何性質(zhì)無關(guān).圖8就是這樣的一個例子，從內(nèi)網(wǎng)點O開始執(zhí)行算法4.1，不會產(chǎn)生需要進行HCT加密的三角形胞腔，僅僅循環(huán)3次便終止算法.另外，此三角剖分既不是文獻［12-14］所定義的分層三角剖分（因為不存在一個擬圈，內(nèi)網(wǎng)點呈分支狀分布（圖中黑色的實心圓點）），也不是文獻［22］中所研究的6度廣義非收縮三角剖分（因為存在邊界網(wǎng)點度數(shù)大于6）.任何與如圖8的三角剖分同胚（不改變其拓?fù)浣Y(jié)構(gòu)簡單拉伸和扭轉(zhuǎn)）的三角剖分下的二元樣條函數(shù)空間（△）的維數(shù)具有非奇異性，符合定理4.2的結(jié)論.事實上，可以更進一步表明，對于任意星型區(qū)域，在部分或全部的三角形胞腔內(nèi)按照圖8的方式添加一些內(nèi)網(wǎng)線和內(nèi)網(wǎng)點，形成的新三角剖分下二元三次一階光滑樣條函數(shù)空間的維數(shù)也具有非奇異性，符合定理4.2的結(jié)論.另外，也可以對一些特殊三角剖分（如圖9所示，由三角形等位線形成的三角剖分）下的二元三次一階光滑樣條函數(shù)空間構(gòu)造一個最小決定集，進而確定其維數(shù).

圖8 一種收縮三角剖分Fig.8 A kind of contraction triangulation

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

致謝西昌學(xué)院校級科研項目（LGLS201808）對本文給予了支持，謹(jǐn)致謝意.