【原】沃羅諾伊圖和格奧爾基·沃羅諾伊

遇見數(shù)學(xué) 2022-03-08

展開全文

1.引言

假如平面上有兩個點(diǎn)和，你想劃分出兩個區(qū)域，一個距離近一些，另一個距離近一些。這里和可能是兩個小學(xué)、兩個郵局或者兩個超市。這個問題不是很難。我們知道兩個區(qū)域的邊界是兩個點(diǎn)的垂直平分線。那么如果有三個點(diǎn)、四個點(diǎn)呢？問題稍微復(fù)雜一點(diǎn)，但也不是很難。我們?nèi)匀豢梢酝ㄟ^兩兩點(diǎn)的垂直平分線來得到。

圖1.三點(diǎn)和四點(diǎn)的沃羅諾伊圖

那么有個點(diǎn)的情況又是如何呢？這就是下面的圖給出的情況了。

圖2.平面上的一般的沃羅諾伊圖/維基百科

這樣的圖叫做沃羅諾伊圖（Voronoi diagram）。這個名字來自烏克蘭數(shù)學(xué)家格奧爾基·費(fèi)奧多謝維奇·沃羅諾伊（Georgy Voronoy，1868－1908）。

2. 沃羅諾伊的生平

圖3. 沃羅諾伊/維基百科

沃羅諾伊于 1868 年 4 月 28 日出生在烏克蘭中北部的茹拉夫卡村（Village of Zhuravka，當(dāng)時屬俄羅斯帝國）。當(dāng)他還在上高中的時候，他就解決并發(fā)表了代數(shù)問題的結(jié)果。高中畢業(yè)后，他去了俄羅斯的圣彼得堡大學(xué)，起初是本科生，但最終在安德烈·馬爾科夫（Andrey Markov，1856–1922）手下成為博士生。1894年，他以“關(guān)于取決于三次方程根的代數(shù)整數(shù)”的碩士論文獲得碩士學(xué)位。同年他成為了華沙大學(xué)的教授。瓦茨瓦夫·謝爾賓斯基（Wac?aw Sierpiński，1882－1969）就是他的一名學(xué)生。1897年，他的博士論文“關(guān)于連續(xù)分?jǐn)?shù)的推廣”獲得通過。他的碩士論文和博士論文都被圣彼得堡科學(xué)院授予了布尼亞科夫斯基數(shù)學(xué)杰出工作獎（Bunyakovsky prize）。此后他研究數(shù)論，他的工作成為了蘇聯(lián)數(shù)學(xué)家伊萬·維諾格拉多夫（Ivan Vinogradov，1891－1983）研究的出發(fā)點(diǎn)；他的方法還被哈代和利特爾伍德使用。1904年他應(yīng)邀在國際數(shù)學(xué)家大會上做報(bào)告。

當(dāng)他年僅40歲時，沃羅諾伊患上了嚴(yán)重的膽結(jié)石。他的肚子異常疼痛。他在日記里寫道：“我在研究中的問題（不定二次形式）方面取得了很大進(jìn)展；然而，與此同時，我的健康越來越差。昨天我第一次對我正在研究的形式理論中的算法有了清晰的認(rèn)識，但同時也遭受了嚴(yán)重的膽絞痛發(fā)作，導(dǎo)致我晚上無法工作，無法整夜睡覺。我好怕我歷經(jīng)千辛萬苦所取得的成果，會隨著我一起消亡。”。遺憾的是，他于1908年11月20日在家鄉(xiāng)去世。他的論文已經(jīng)寫了28頁，但他的主要結(jié)果還是永久地消失了。

雖然他的生命是短暫的，但他留下了令人矚目的遺產(chǎn)。除了謝爾賓斯基，他對俄國數(shù)學(xué)家鮑里斯·德勞內(nèi)（Boris Delaunay，1890－1980）有重要影響。他的兒子成為杰出的移植外科醫(yī)生，他于1933年進(jìn)行了世界上第一個人體對人體的腎臟移植手術(shù)。小沃羅諾伊自愿為烏克蘭中央議會服務(wù)并參加了1918年的克魯季戰(zhàn)役（Battle of Kruty）。他的女兒則成為了烏克蘭語的教師。

沃羅諾伊圖

沃羅諾伊最大的貢獻(xiàn)是沃羅諾伊圖。沃羅諾伊圖也被稱作狄利克雷鑲嵌。這是因?yàn)榈依死自?850年研究二次型的時候使用過這個思想。笛卡爾在1644年也非正式地使用過它。1854年，英國一位醫(yī)生曾經(jīng)使用沃羅諾伊圖來說明“1854年寬街霍亂爆發(fā)事件”中死去的人都居住在離寬街的公共水泵不遠(yuǎn)處。而沃羅諾伊則是（在1908年）第一位定義并研究了這個課題的數(shù)學(xué)家。

前面我們已經(jīng)看到，沃羅諾伊圖是一種以距離出發(fā)的空間分割算法。給定一個距離空間和一個下標(biāo)集K，令為X中的一個非空子集順序組（基點(diǎn)的集合，稱作種子、站點(diǎn)或生成器）。對應(yīng)于點(diǎn)集的沃羅諾伊原胞（Voronoi cell，也稱為沃羅諾伊區(qū)域），記為,是空間中到的距離都不大于到其他點(diǎn)的那些點(diǎn)，即

其中是的距離函數(shù)。那么順序組就是一個沃羅諾伊圖。那么順序組就是一個沃羅諾伊圖?；c(diǎn)集合可以是無限集合，這在幾何數(shù)論和結(jié)晶學(xué)里有所應(yīng)用，但通常情況下，它是一個有限的集合。在歐幾里得距離空間里，假定每一個都是一個點(diǎn)并且它們是有限多的。那么每一個沃羅諾伊原胞都是一個凸多胞形。但一般地，沃羅諾伊原胞不一定是凸形，甚至不一定是連通的。

注意我們對沃羅諾伊的通常印象都是在歐幾里得距離空間中的。如果我們換一個距離函數(shù)，那么得到的沃羅諾伊圖就完全不同了。下面是與圖2中同樣的引入點(diǎn)組條件下使用曼哈頓距離所得到的沃羅諾伊圖：

圖4.以曼哈頓距離劃分出的沃羅諾伊圖/維基百科

曼哈頓距離（Manhattan distance）也稱為計(jì)程車幾何。這是由十九世紀(jì)的赫爾曼·閔可夫斯基（Hermann Minkowski，1864－1909）所創(chuàng)辭匯，用以標(biāo)明兩個點(diǎn)上在標(biāo)準(zhǔn)坐標(biāo)系上的絕對軸距之總和。例如在平面上，坐標(biāo)的點(diǎn)與坐標(biāo)的點(diǎn)的曼哈頓距離為：

這個距離經(jīng)常會被計(jì)算機(jī)系的教授用來布置作業(yè)。沃羅諾伊和閔可夫斯基的研究有相交。他們在1904年的國際數(shù)學(xué)家大會上交談中發(fā)現(xiàn)了共同的興趣。

4. 德勞內(nèi)三角化

一個與沃羅諾伊圖相關(guān)的是在計(jì)算幾何領(lǐng)域的一個概念：德勞內(nèi)三角化。在這一節(jié)里，我們將我們的討論限制在平面上的歐幾里得距離空間里。給定平面上的一個點(diǎn)集P。P的三角化就是以這些點(diǎn)為頂點(diǎn)做三角剖分。顯然，P可以有不同的三角剖分。比如，下面的四個點(diǎn)有兩種三角剖分。

圖5.四個點(diǎn)的兩種三角剖分

我們應(yīng)該選哪一個呢？是不是左邊的一個看上去更舒服一些呢？想象一下，我們希望能為我們所用的三角形越正規(guī)越好，也就是說，越接近等邊三角形越好，盡管我們不可能保證它們每一個都是等邊三角形。至少我們可以希望三角形的三個內(nèi)角中沒有一個太小，否則就會出現(xiàn)右邊的那個樣子。事實(shí)上，當(dāng)一個三角剖分中有太小的角度時，會在計(jì)算中出現(xiàn)較大的誤差。讓我們把上面5圖中的三角形的外接圓都畫出來：

圖6.三角剖分及其外接圓

注意在圖6左圖中，兩個三角形的外接圓都不包含另一個點(diǎn)；而在圖6右圖中，兩個三角形的外接圓則把另一個點(diǎn)包括進(jìn)去了。這就引出了德蘭內(nèi)三角剖分的定義：平面上的點(diǎn)集P的德勞內(nèi)三角化是一種三角剖分，使得在P中沒有點(diǎn)嚴(yán)格處于中任意一個三角形外接圓的內(nèi)部。德蘭內(nèi)三角化的意義就是它最大化了此三角剖分中三角形的最小角。也就是說，此算法盡量避免出現(xiàn)“極瘦”的三角形，就像圖5中的右圖那樣。此算法命名來源于俄國數(shù)學(xué)家鮑里斯·德勞內(nèi)，以紀(jì)念他自1934年在此領(lǐng)域的工作。

說了這么多，那么德勞內(nèi)三角化與沃羅諾伊圖是什么關(guān)系呢？答案是：用圖論的語言說，這個沃羅諾伊圖的對偶是這個德勞內(nèi)三角剖分。給定一個德勞內(nèi)三角剖分，頂點(diǎn)的集合是P。假定P中沒有三點(diǎn)共線，也沒有四點(diǎn)共圓。連接那些外接圓的圓心就產(chǎn)生了以P為種子的沃羅諾伊圖。圖論中的對偶概念已經(jīng)超出了本文的范圍。下面圖7的左圖是一個德勞內(nèi)三角化的例子，所有三角形外接圓的圓心以藍(lán)點(diǎn)表示；連接外接圓圓心即產(chǎn)生沃羅諾伊圖，在此以藍(lán)線表示（見右圖）。

圖7. 德勞內(nèi)三角剖分和沃羅諾伊圖

5. 沃羅諾伊圖的生成

一般說來，生成沃羅諾伊圖的算法有兩種：一種是直接生成的算法，另一種是先生成德勞內(nèi)三角刨分后再取其對偶。這是計(jì)算幾何中的課題了。

Python有一個開源的算法庫和數(shù)學(xué)工具包SciPy。其中有現(xiàn)成的算法可以生成沃羅諾伊圖和德勞內(nèi)三角刨分。讓我們選平面上的四個點(diǎn)：和。在Python3環(huán)境下執(zhí)行下面的程序：

import numpy as np
# Given a set of seed points
points = np.array([[0,0], [2,1], [3,2], [1,3]])

# Call Voronoi method
from scipy.spatial import Voronoi, voronoi_plot_2d
vor = Voronoi(points)

# Plot it:
import matplotlib.pyplot as plt
fig = voronoi_plot_2d(vor)
plt.show()

我們可以看到下面的圖像：

圖8. Python程序生成的沃羅諾伊圖

互聯(lián)網(wǎng)上有一些不錯的沃羅諾伊圖生成器，比如：

https://cfbrasz./Voronoi.html
https://www./calculator/ejatebvup4
https://www./maps/voronoi/
http://www./projects/voronoi/
https://socr./HTML5/others/Voronoi_App/

也有不少人自己把沃羅諾伊圖算法編寫成了程序。直接算法中最著名的是Fortune算法，也叫平面掃描算法。有興趣的讀者可以自己找相關(guān)讀物學(xué)習(xí)。

6. 沃羅諾伊圖的應(yīng)用

沃羅諾伊圖在幾何、李群、凝聚態(tài)物理學(xué)、晶體學(xué)、建筑學(xué)、地球物理學(xué)、氣象學(xué)、空間分布數(shù)據(jù)分析、電腦圖像、信息系統(tǒng)等許多領(lǐng)域有廣泛的應(yīng)用，盡管有時不是以這個名字出現(xiàn)的。我們以沃羅諾伊圖的例子結(jié)束本文。