潘申潤,李滿枝

(1.福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院,福州 350117；2.海南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,海口 571158)

0 引言

Thiessen-多邊形又稱為Voronoi diagram,是由平面中的離散點所形成的三角形外接圓的圓心所形成的多邊形.二維平面上Thiessen-多邊形與Voronoi diagram所指的是同一類圖形,因而長期以來人們習(xí)慣性地將Voronoi-多面體也稱為Thiessen-多面體[1-4].但是本研究發(fā)現(xiàn)Thiessen-多面體與三維Voronoi diagram的形成機(jī)理不同,故Thiessen-多面體與Voronoi-多面體的定義與性質(zhì)均存在不同.

本研究對二維Thiessen-多邊形的定義進(jìn)行拓展,給出Thiessen-多面體新的定義,研究其性質(zhì),發(fā)現(xiàn)該多面體的體積比原定義的體積更小,即Thiessen-多面體是Voronoi-多面體的改進(jìn)結(jié)果.

1 Thiessen-多面體的提出

本研究將二維平面上的Thiessen-多邊形拓展為三維空間下的Thiessen-多面體.

首先，將平面離散點拓展為空間離散點.由于在三維空間中最簡單的空間圖形為四面體,從而需要保證在中心離散點外存在至少4個外圍離散點,對這4個外圍離散點要求它們不在一個平面上,且由它們所形成的四面體包含中心離散點.從而本研究可以得到Thiessen-四面體的形成條件,即在Thiessen-多面體的中心離散點周圍存在n個外圍離散點(n≥4),這n個點不共面、不共球,且由這n個離散點所形成的多面體包含中心離散點.

其次，將三角形拓展為四面體.在Thiessen-多邊形形成過程中,將二維平面中的中心離散點與相鄰的兩個外圍離散點互相連接形成一個三角形.而在三維空間中,考慮將平面上的三角形拓展為空間中的四面體,即選取中心離散點為四面體的一個頂點,將相鄰的三個外圍離散點進(jìn)行連接形成該四面體的底面.這樣依次選取中心離散點外的n個外圍離散點構(gòu)建n個不同四面體的底面,從而形成n個四面體.

再次，將外接圓與外接圓圓心拓展為外接球與外接球球心.在Thiessen-多邊形的形成過程中,將中心離散點與外圍離散點進(jìn)行連接形成若干個三角形,之后繪制各個三角形的外接圓并標(biāo)記圓心位置.在n中圓和球都是緊集,本研究在形成n個四面體的基礎(chǔ)上繪制出n個四面體的外接球并標(biāo)記這n個外接球球心位置,由于要求外圍離散點不共面且不共球,從而這個外接球的球心必不重合.

最后，將Thiessen-m多邊形拓展為Thiessen-多邊形的n個頂點.在Thiessen-多邊形的形成過程中,m個外圍離散點形成了m個三角形并標(biāo)記了m個外接圓的圓心,從而形成了一個Thiessen-m邊形,即若存在m個外圍離散點,則形成的Thiessen-多邊形具有m條邊.而在Thiessen-多面體的形成過程中,n個外圍離散點所形成的n個四面體,可繪制出n個外接球并標(biāo)記出這個外接球的球心位置,由這個外接球球心所形成的Thiessen-多面體的頂點個數(shù)為n.

在對以上內(nèi)容進(jìn)行拓展后,得到了一個Thiessen-多面體.

命題1(Thiessen-多面體的形成條件一) 外圍離散點所形成的多邊形包含中心離散點.

命題1的判定條件有以下兩類：一是先確定有可能穿過的包含k個頂點的所有的折線,然后對計算射線所穿透的鏈的數(shù)目進(jìn)行判定[5]；二是通過將多面體的面片和多邊形的邊組織成層次結(jié)構(gòu)，運用二分查找算法判定[6].

命題2(Thiessen-多面體的形成條件二) 中心離散點與任意四個相鄰的外圍離散點不共面、不共球,即n個外圍離散點所形成n個四面體的n個外接球球心不重合.

命題3(Thiessen-多面體的形成過程) ①選取中心離散點將其與外圍3個相鄰的離散點進(jìn)行連接形成一個四面體,從而根據(jù)外圍離散點的數(shù)目n形成n個四面體[圖1(a)].②對于四面體按其面是否相鄰,依次對面相鄰的四面體進(jìn)行排序.③繪制各個四面體的外接球并標(biāo)記外接球球心[圖1(b)].④依次連接各個外接球球心形成面,生成一個以外接球球心為頂點的多面體O1O2O3O4O5O6[圖1(c)].

圖1 Thiessen-多面體的形成過程

由圖1可知，我們將由命題3所形成的多面體O1O2O3O4O5O6稱為Thiessen-多面體,稱M為中心離散點,而A,B,C,D,E和F為外圍離散點，O1,O2,O3,O4,O5和O6為Thiessen-多面體頂點.

定義1(Thiessen-多面體的新定義) 根據(jù)Delaunay三角網(wǎng)形成法則,對M點相鄰的n個離散點進(jìn)行編號,以M為頂點,對于編號相鄰的三點形成四面體的底面三角形,形成n個四面體.記Q(n)為這n個四面體外接球球心所組成的點集,則以Q(n)為頂點所形成的多面體稱為以M為中心離散點的Thiessen-多面體.

2 Thiessen-多面體的性質(zhì)

2.1 Thiessen-多面體的頂點、面、棱的性質(zhì)

為更好地給出Thiessen-多面體頂點、面、棱的性質(zhì),先給出關(guān)于無效多面體底面、無效多面體與無效多面體面的定義,并給出了多面體歐拉定理作為引理.

定義2由非相鄰的外圍離散點所形成的四面體底面稱為無效四面體底面；由無效四面體底面所形成的四面體稱為無效四面體.

定義3由外接球球心組成點集Q(n)的某些元素所形成的一個面Γ,若存在Q(n)中的剩余元素分布在面Γ的兩側(cè),則稱面Γ為無效Thiessen-多面體面.

引理1(多面體歐拉定理) 簡單多面體的頂點數(shù)V、面數(shù)F及棱數(shù)E間有如下恒等式關(guān)系：

V+F-E=2.

①

注：可以考慮通過類比法證明該引理成立[7].

性質(zhì)1中心離散點與n個外圍離散點(n≥4)所形成的Thiessen-多面體具有n個頂點.

證明結(jié)合命題1與命題2,可以發(fā)現(xiàn)由中心離散點與n個相鄰的外圍離散點形成了n個四面體,而這n個四面體對應(yīng)著有n個外接球的球心恰好是點集Q(n)的元素,從而此時所產(chǎn)生的Thiessen-多面體具有n個頂點.

性質(zhì)2中心離散點與n個外圍離散點(n≥4)所形成的Thiessen-多面體最多具有(2n-4)個面，最多具有(3n-6)條棱.

2.2 Thiessen-多面體的凹凸性.

凸多面體是指把多面體的任何一個面伸展成平面,如果所有其他各面都在這個平面的同側(cè)[8-9].

性質(zhì)3任一Thiessen-多面體是凸多面體.

證明在排除無效多面體面之后,Thiessen-多面體面的個數(shù)最多為2n-4,且這(2n-4)個面均可以認(rèn)定為是引理1中所描述的面ω.由于Thiessen-多面體的特殊形成條件,則任一Thiessen-多面體都是凸多面體.

3 Thiessen-多面體與Voronoi-多面體

3.1 Thiessen-多面體與Voronoi-多面體的定義

定義4(Voronoi-多面體的定義) 中心離散點與其近鄰各外圍離散點間連線的垂直平分面所圍成的[10]、具有最小體積的多面體稱為Voronoi-多面體[11].

定義5(Thiessen-多面體的另一定義) 假設(shè)V={V1,V2,…Vn}(n≥4)是3空間上的一個點集,并且這些點不共線、不共球.記ω(A,B)為點A,B間的垂直平分面,設(shè)P為3空間上的點,從而定義新的一個點集我們將由點集Q(n)為頂點所形成的多面體稱為以P為中心離散點的Thiessen-多面體.

相較Thiessen-多面體與Voronoi-多面體的形成過程及定義，我們不難看出其中存在的區(qū)別,即Thiessen-多面體的形成在于規(guī)則地標(biāo)記外接球的球心,根據(jù)外接球球心所組成的點集Q(n)為多面體頂點所形成的；而Voronoi-多面體則是由出中心離散點與其近鄰各外圍離散點間連線的垂直平分面所圍成的多面體.

3.2 Thiessen-多面體與Voronoi-多面體的圖形

為更為直觀地展示Thiessen-多面體與Voronoi-多面體的區(qū)別,我們將同樣條件下單獨形成的Voronoi-多面體(圖2)，它為相同條件下所形成的Voronoi-多面體，它與Thiessen-多面體進(jìn)行對比(比對情況圖3),其中Thiessen-多面體為以中心離散點M與外圍離散點A,B,C,D,E,F所形成的多面體.

二者最大的區(qū)別在于:Thiessen-多邊形存在6個頂點、8個面;Voronoi-多面體存在8個頂點、6個面.可見相同條件下Voronoi-多面體的部分頂點與Thiessen-多面體的頂點和面是重合的.

3.3 Thiessen-多面體與Voronoi-多面體的新理論

由圖3能夠直觀地看出Thiessen-多面體與Voronoi-多面體是兩個不同的圖形,但兩者之間存在著一定的聯(lián)系.

定理1Thiessen-多面體與Voronoi-多面體是兩個不同的圖形,當(dāng)且僅當(dāng)Thiessen-多面體為錐體時,Thiessen-錐體與Voronoi-錐體是重合的.

證明Thiessen-多面體與Voronoi-多面體是兩個不同的圖形,其最大的區(qū)別在于頂點與面的個數(shù).性質(zhì)1說明了n個外圍離散點(n≥4)所形成的Thiessen-多面體具有n個頂點；而Voronoi-多面體是由中心離散點與其近鄰n個外圍離散點(n≥4)間連線的垂直平分面所圍成的、具有最小體積的多面體,從而Voronoi-多面體具有n個面,這個面是由其n個外圍離散點所提供的[12].由此,可以說明當(dāng)空間一個中心離散點的外圍存在n個外圍離散點(n≥4)時,所產(chǎn)生的的Thiessen-多面體具有n個頂點,Voronoi-多面體具有n個面,即Thiessen-多面體與Voronoi-多面體是兩個不同的圖形.但我們也應(yīng)當(dāng)注意到,若一個空間圖形具有n個頂點與n個面時,此時Thiessen-多面體與Voronoi-多面體重合.由棱錐的性質(zhì)可以說明了Thiessen-錐體具有n個頂點與n個面,并且這n個面分別是中心離散點與n個外圍離散點的垂直平分面,即Thiessen-錐體與Voronoi-錐體是重合的.

定理2Thiessen-多面體可看作若干個平面切割Voronoi-多面體所得出.

由定理2可以給出Thiessen-多面體的一個新的定義.

定義6(Thiessen-多面體的另一個新定義) 在中心離散點M與外圍離散點形成Voronoi-多面體的基礎(chǔ)上標(biāo)記出外接球球心所組成的點集Q(n)中的所有元素,取過Q(n)的3個元素形成一個平面P,使得Q(n)中的剩余(n-3)個元素在該面的同一側(cè),Voronoi-多面體頂點所組成過的點集R(p)中的元素在該面的另一側(cè)[17],用這樣的P對Voronoi-多面體進(jìn)行切割,剩余的部分為Thiessen-多面體.

定理3由中心離散點與外圍離散點所形成的Thiessen-多面體嵌入在相同情況下形成的Voronoi-多面體中.

證明Thiessen-錐體與Voronoi-錐體重合時,此時可以認(rèn)定Thiessen-錐體嵌入在Voronoi-錐體內(nèi).以下考慮非Thiessen-錐體的情況,由定義6可知,Thiessen-多面體可以由同等條件下的Voronoi-多面體通過平面切割的方式得到,Thiessen-多面體是在Voronoi-多面體中通過形成新增側(cè)面所形成,且該側(cè)面為Thiessen-多面體的一個面,它截去了Voronoi-多面體的一個頂點.經(jīng)過若干次平面的切割后剩余的Voronoi-多面體嵌入在原有Voronoi-多面體中.從而推出由中心離散點與外圍離散點所形成的Thiessen-多面體嵌入在相同情況下形成的Voronoi-多面體中.

定理4由中心離散點與外圍離散點所形成的Thiessen-多面體的體積與表面積小于等于相同情況下形成的Voronoi-多面體的體積與表面積.

圖4 Voronoi-多面體經(jīng)平面ABC切割后被截去的棱錐D-ABC

對于任一棱錐,底面積恒小于其他面的總和,即SABC≤SDAB+SDBC+SDAC,圖中SDAB,SDBC,SDAC為Voronoi-多面體表面積的一部分,經(jīng)過平面ABC的截取后,面ABC為新增側(cè)面,即此時的Thiessen-多面體的面,從而經(jīng)過有限次的平面切割之后剩余的部分(Thiessen-多面體)的表面積小于Voronoi-多面體的表面積,即由中心離散點與外圍離散點所形成的Thiessen-多面體的體積與表面積小于等于相同情況下形成的Voronoi-多面體的體積與表面積.

至此,我們討論了Thiessen-多面體與Voronoi-多面體的區(qū)別與聯(lián)系,并得到了幾個重要的結(jié)論,也證明了Voronoi-多面體的體積并非最小,Thiessen-多面體是同等條件下形成的最小體積的多面體.為后續(xù)改進(jìn)與優(yōu)化現(xiàn)有利用Voronoi-多面體構(gòu)造的數(shù)學(xué)模型[18-19]提供理論依據(jù).

5 結(jié)論

本文主要介紹了一個全新的概念——Thiessen-多面體.一組空間的中心離散點與其相鄰的三個外圍離散點形成四面體,其外接球球心作為頂點構(gòu)造出Thiessen-多面體.

根據(jù)這個新定義,推導(dǎo)了Thiessen-多面體的性質(zhì)：①若Thiessen-多面體的頂點數(shù)為n,則最大的面數(shù)為2(n-2),最大的棱數(shù)為3(n-2);②Thiessen-多面體是凸多面體.

通過比較Thiessen-多面體與Voronoi-多面體的定義與性質(zhì),得到了幾個結(jié)論:①提出并證明了Thiessen-多面體與Voronoi-多面體是兩類不同的圖形;②改進(jìn)了Voronoi-多面體的一些理論,提出了在同等條件下體積最小圖形的構(gòu)造過程;③Thiessen-多面體可看作若干個平面切割Voronoi-多面體所得出;④Thiessen-多面體是嵌入在Voronoi-多面體中.這些新的理論與定理都將為進(jìn)一步推導(dǎo)出Thiessen-多面體的新應(yīng)用提供理論依據(jù).

這些研究工作還值得進(jìn)一步拓展,具體可以考慮以下幾個方面：

1)推導(dǎo)Thiessen-多面體的更多性質(zhì).對Thiessen-多面體的其他性質(zhì)做進(jìn)一步補(bǔ)充和完善；

2)Thiessen-多面體的應(yīng)用.在后續(xù)的研究中將重點研究根據(jù)Thiessen-多面體的性質(zhì),建立相應(yīng)的數(shù)學(xué)模型以解決空間分割或計算體積等問題；

3)將Thiessen-多面體由三維拓展至更高維.三維空間下的Thiessen-多面體是由二維平面中的Thiessen-多面體拓展而得出的.從而可以考慮將空間維度進(jìn)一步拓展至更高維度,以研究在高維空間下所形成Thiessen-空間體及其性質(zhì)，因此將得到一系列新的概念與性質(zhì),并利用這些新理念解決社會生活中的實際問題.