潘申潤(rùn),李滿枝

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

0 引言

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

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

1 Thiessen-多面體的提出

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

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

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

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

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

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

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

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

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

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

圖1 Thiessen-多面體的形成過(guò)程

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

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

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

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

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

定義2由非相鄰的外圍離散點(diǎn)所形成的四面體底面稱為無(wú)效四面體底面；由無(wú)效四面體底面所形成的四面體稱為無(wú)效四面體.

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

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

V+F-E=2.

①

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

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

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

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

2.2 Thiessen-多面體的凹凸性.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

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

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

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

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