我們使用標(biāo)準(zhǔn)容器和算法討論Voronoi圖的簡單變體，這些容器和算法提供的性能比暴力法更好。

介紹

基于邊界的Voronoi圖

點(diǎn)位置查詢

簡單變體的想法

蠻力法

網(wǎng)格法

倒排列表

計(jì)算復(fù)雜度

更新操作

Voronoi圖的更高級的變體

C ++實(shí)現(xiàn)

Voronoi圖的可視化和距離變換

性能測試

使用C ++代碼

與C＃實(shí)現(xiàn)的比較

德勞內(nèi)三角剖分

參考文獻(xiàn)

介紹

Voronoi圖（參見圖1）是具有許多應(yīng)用程序的基本幾何結(jié)構(gòu)。有關(guān)更詳細(xì)的描述，請參見Wikipedia [1]中的文章及其參考。

圖1：平面中一組點(diǎn)的Voronoi圖。

不幸的是，Voronoi圖的有效編程表示需要相當(dāng)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。開發(fā)和維護(hù)這些數(shù)據(jù)結(jié)構(gòu)的高成本是在實(shí)踐中充分利用這一強(qiáng)大的數(shù)學(xué)概念的嚴(yán)重障礙。

在這里，我們討論使用可互換STL容器的可負(fù)擔(dān)且有效的Voronoi圖。這種方法的主要優(yōu)點(diǎn)是表示簡單，開發(fā)和維護(hù)成本低以及對各種用戶算法的適應(yīng)性。好處是以性能為代價(jià)的，但是，它比暴力方法要好得多。Voronoi圖的建議變體對于快速開發(fā)需要Voronoi圖功能的算法，以及開發(fā)Voronoi圖的高級和高效表示形式應(yīng)該是有用的。

根據(jù)定義，Voronoi圖表示將二維空間細(xì)分為由一組輸入點(diǎn)誘導(dǎo)的區(qū)域，這些點(diǎn)在傳統(tǒng)術(shù)語中稱為站點(diǎn)。每個(gè)區(qū)域都有一個(gè)多邊形邊界，其中包含最接近該區(qū)域站點(diǎn)的平面的所有點(diǎn)。這些區(qū)域也稱為Voronoi細(xì)胞。

圖2： Voronoi圖的基于邊界的表示圖。兩個(gè)相鄰單元格的公共邊界元素用紅色繪制。

Voronoi圖的廣泛使用的基于邊界的表示形式，如圖2所示，存儲了位置，單元，邊緣和頂點(diǎn)的集合。這些表示的復(fù)雜性不僅與數(shù)據(jù)集相關(guān)，而且與支持不同類型表示形式的元素之間的鄰接關(guān)系的需求有關(guān)。例如，邊緣必須鏈接到單元格邊界中的上一條和下一條邊緣，此外，該邊緣必須存儲到該邊界所包圍的單元格的至少一個(gè)鏈接。這些表示形式對于有效遍歷Voronoi圖和計(jì)算Voronoi單元的參數(shù)（例如面積和周長）很有用。

應(yīng)用程序中所需的Voronoi圖的主要功能之一是平面點(diǎn)定位算法，該算法針對給定的查詢點(diǎn)查找包含該點(diǎn)的像元。點(diǎn)位置問題非常重要。在實(shí)踐中出現(xiàn)的許多類型的特定問題可以簡化為點(diǎn)位置問題。一個(gè)典型的示例是涉及計(jì)算居住在購物中心區(qū)域內(nèi)的客戶數(shù)量的任務(wù)。

盡管有豐富的數(shù)據(jù)集，但是基于邊界的表示方法沒有提供比具有線性運(yùn)行時(shí)間的搜索更好的功能。一種方法是將多邊形中的測試點(diǎn)應(yīng)用于Voronoi單元。另一種方法是通過計(jì)算從查詢點(diǎn)到每個(gè)站點(diǎn)的距離來找到最近的站點(diǎn)。為了使用對數(shù)運(yùn)行時(shí)間進(jìn)行有效的搜索操作，Voronoi圖的表示應(yīng)使用基于R樹或有向無環(huán)圖（DAG）的空間索引。另一個(gè)高級數(shù)據(jù)結(jié)構(gòu)的開發(fā)和集成使有效的Voronoi圖的實(shí)現(xiàn)和維護(hù)變得頗具挑戰(zhàn)性，并且成本很高。

Voronoi圖的實(shí)際變體的想法是通過存儲和使用盡可能少的數(shù)據(jù)集來降低表示的復(fù)雜性。在建議的最小變體中，Voronoi圖僅由一組站點(diǎn)表示。該表示的第二個(gè)元素是最近鄰居搜索的算法。該算法旨在支持Voronoi圖的功能：點(diǎn)位置，查找站點(diǎn)的鄰居以及構(gòu)建單元格邊界。如果最近鄰居搜索的實(shí)現(xiàn)簡單，則此方法可提供這種Voronoi圖表示的主要優(yōu)點(diǎn)-降低開發(fā)和維護(hù)成本。該變體的另一個(gè)好處是最小的空間需求。

在開發(fā)的早期階段，考慮并實(shí)施Voronoi圖的蠻力變體是合理的。它基于簡單的算法，該算法計(jì)算查詢點(diǎn)與每個(gè)Voronoi站點(diǎn)之間的距離，并找到具有第一個(gè)最小距離的站點(diǎn)。實(shí)施蠻力變體的簡便性以犧牲用戶算法所需的操作效率為代價(jià)。該方法具有線性運(yùn)行時(shí)間。對于大型數(shù)據(jù)集來說太慢了。

Voronoi圖的簡單表示的主要問題是，是否有可能在不開發(fā)點(diǎn)位置查詢所需的復(fù)雜空間數(shù)據(jù)結(jié)構(gòu)的情況下提高最近鄰居搜索的效率。

蠻力方法的低效率可以通過流行的網(wǎng)格方法解決。此方法的最簡單變體是構(gòu)建大小相等的方形單元。每個(gè)網(wǎng)格單元均存儲其包含的點(diǎn)的列表。

圖3：網(wǎng)格方法的圖示。最近鄰居搜索算法計(jì)算查詢點(diǎn)（紅色）和灰色單元中的點(diǎn)之間的距離。

搜索從包含查詢點(diǎn)的單元格開始，然后在與訪問的單元格相鄰的單元格中繼續(xù)進(jìn)行搜索（參見圖3）。當(dāng)查詢點(diǎn)與最接近的未訪問單元格之間的距離大于查詢點(diǎn)與已處理數(shù)據(jù)子集中的點(diǎn)之間的最小距離時(shí)，搜索將停止。

網(wǎng)格方法比基于空間數(shù)據(jù)結(jié)構(gòu)的方法簡單得多，但是它并不完全瑣碎，并且有許多限制。當(dāng)空間數(shù)據(jù)的分布均勻時(shí)，此方法可提供最佳性能。像元的最佳大小取決于數(shù)據(jù)的密度。當(dāng)網(wǎng)格中有太多的空單元格或一個(gè)單元格中的平均點(diǎn)數(shù)太大時(shí)，此方法的性能會降低。即使空間數(shù)據(jù)的分布是均勻的，也必須重建網(wǎng)格單元，以避免由于空間數(shù)據(jù)集中的點(diǎn)數(shù)變化而導(dǎo)致性能損失。重建操作是網(wǎng)格方法的主要缺點(diǎn)。它使實(shí)現(xiàn)復(fù)雜化，并可能導(dǎo)致用戶算法的性能下降。

在本文中，我們將重點(diǎn)介紹具有許多吸引人的功能的“反向列表”或“反向文件”方法。從實(shí)現(xiàn)的角度來看，這是最簡單的方法之一。它比蠻力法稍難，但比網(wǎng)格法和空間索引更簡單。在性能方面，盡管不能與使用空間索引結(jié)構(gòu)的方法競爭，但與強(qiáng)力方法相比，該方法提供了相當(dāng)合理的改進(jìn)。與網(wǎng)格方法不同，此方法不需要重新構(gòu)建操作，因?yàn)榭臻g數(shù)據(jù)集會增加或縮小。

The method of inverted list is based on an ordered data set. It imposes an order on elements using the values of one of the attributes. For a set of two dimensional points, this requirement implies that the set of Voronoi sites can be sorted by X-coordinate (or Y-coordinate) of a point. However, in computational geometry, a more suitable option is to use lexicographic ordering.

幫助開發(fā)新的更有效的最近鄰搜索算法的關(guān)鍵發(fā)現(xiàn)是站點(diǎn)的字典順序顯著減小了搜索范圍。如下圖4所示，該順序使算法避免在距查詢點(diǎn)很遠(yuǎn)的區(qū)域中進(jìn)行搜索。因此，與無序集合不同，無需計(jì)算查詢點(diǎn)與每個(gè)站點(diǎn)之間的距離。這個(gè)事實(shí)說明了通過暴力方法獲得的性能提升。

圖4：在一組有序點(diǎn)中的最近鄰居搜索。查詢點(diǎn)的X坐標(biāo)（紅色）與向前和向后順序搜索的兩個(gè)起點(diǎn)之間的紅線段相交?；疑珔^(qū)域包含該算法要訪問的點(diǎn)的最小子集。

改進(jìn)的最近鄰搜索算法具有兩個(gè)階段。首先，該算法為給定的查詢點(diǎn)找到站點(diǎn)集中的初始位置。此位置提供兩個(gè)站點(diǎn)，它們的X坐標(biāo)構(gòu)成范圍，其中包含查詢點(diǎn)的X坐標(biāo)。然后，使用初始位置以按站點(diǎn)的升序和降序的順序開始兩個(gè)連續(xù)搜索。搜索向前或向后移動(dòng)，并計(jì)算查詢點(diǎn)與當(dāng)前站點(diǎn)之間的距離。當(dāng)查詢點(diǎn)和當(dāng)前站點(diǎn)的X坐標(biāo)之間的差的絕對值大于所計(jì)算的從查詢點(diǎn)到已處理子集中站點(diǎn)的最小距離時(shí)，每次搜索都會停止。

以下C ++代碼說明了使用此算法的正向搜索來計(jì)算最小距離：

while ( it_cur != it_end ) {
dist_cur = Distance ( *it_cur , pnt ) ;
dist_x = fabs( it_cur->X() - pnt.X() ) ;

if ( dist_cur < dist_min )
dist_min = dist_cur ;

if ( dist_x > dist_min )
break ;

++it_cur ; }12345678910111213

這段代碼僅比蠻力方法中的典型實(shí)現(xiàn)稍長：

for ( ; it_cur != it_end ; ++it_cur ) {
dist_cur = Distance ( *it_cur , pnt ) ;

if ( dist_cur < dist_min )
dist_min = dist_cur ; }1234567

該算法的性能由處理的第二階段決定。平均而言，每個(gè)順序搜索的運(yùn)行時(shí)間與站點(diǎn)數(shù)的平方根成正比。搜索初始位置更加有效。在有序容器中，最壞情況下的運(yùn)行時(shí)間為對數(shù)。

從理論上講，平方根運(yùn)行時(shí)間看起來并不令人印象深刻。但是，與蠻力搜索相比，所討論的算法的性能提高了幾個(gè)數(shù)量級。例如，當(dāng)Voronoi站點(diǎn)的數(shù)量為10,000時(shí)，該算法比線性搜索快100倍。

在Voronoi圖的上下文中，討論的最近鄰搜索算法的重要優(yōu)點(diǎn)之一是對矩形范圍查詢的有效支持。它可以用于查找站點(diǎn)的所有鄰居，并在一遍算法中構(gòu)造其單元。

該算法的另一個(gè)優(yōu)點(diǎn)是可以通過各種方法和比較操作對一組二維點(diǎn)進(jìn)行排序。這個(gè)事實(shí)對于優(yōu)化特定應(yīng)用程序中最近鄰居搜索的性能很有用?？梢酝ㄟ^使用到線上的預(yù)計(jì)距離對點(diǎn)站點(diǎn)進(jìn)行排序來實(shí)現(xiàn)優(yōu)化，這最適合給定的站點(diǎn)分布。

到目前為止，我們已經(jīng)討論了不會修改Voronoi圖的簡單算法。許多現(xiàn)實(shí)世界的應(yīng)用程序不僅需要遍歷和搜索，還需要插入和擦除操作，這些操作會更改站點(diǎn)和單元的數(shù)量并修改單元的邊界。在此類應(yīng)用程序中，執(zhí)行更新操作的性能和簡便性很重要。

在計(jì)算幾何中，對空間數(shù)據(jù)結(jié)構(gòu)的有效更新操作尤其具有挑戰(zhàn)性。它們僅適用于特定的輸入，假定特定的數(shù)據(jù)分布類型以及插入和刪除的順序。與理想輸入的任何偏差都會導(dǎo)致平衡和性能問題。更新操作會使不變式無效并且算法必須重新構(gòu)建表示形式的數(shù)據(jù)集的情況并不罕見。

擬議的Voronoi圖的簡單變體的優(yōu)點(diǎn)在于，它完全避免了所有這些困難。為了獲得所需的有效更新操作，選擇代表一組站點(diǎn)的合適數(shù)據(jù)結(jié)構(gòu)就足夠了。平衡的搜索樹是此任務(wù)的理想選擇。除了有效的搜索和遍歷之外，它們還支持對數(shù)運(yùn)行時(shí)間的插入和擦除。

盡管Voronoi圖的簡單變體不存儲單元和邊的詳細(xì)空間分區(qū)數(shù)據(jù)集，但可以在此幾何結(jié)構(gòu)的許多應(yīng)用中使用。最近鄰居搜索通過查找其站點(diǎn)的所有鄰居，可以構(gòu)造Voronoi單元的邊界。顯然，與基于邊界的Voronoi圖相比，計(jì)算單元的周長和面積效率較低，但是此方法的性能對于某些應(yīng)用程序可以接受。

另一個(gè)合理的選擇是在Voronoi圖的基于邊界的表示中使用討論的最近鄰居搜索。這種簡單的算法為使用復(fù)雜數(shù)據(jù)結(jié)構(gòu)（例如https://www./）的空間索引方法提供了一種替代方法。但是，它要求將一組站點(diǎn)存儲在有序容器中。

Voronoi圖的簡單變體可以用多種編程語言實(shí)現(xiàn)。C ++標(biāo)準(zhǔn)庫提供了強(qiáng)大的功能，使您能夠以最小的努力開發(fā)許多編程解決方案。我們將利用STL容器和算法來實(shí)現(xiàn)所討論的思想。

Voronoi圖的簡單變體的性能主要取決于代表一組站點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。STL具有幾種類型的基本數(shù)據(jù)結(jié)構(gòu)，它們支持容器和迭代器的統(tǒng)一接口。這一事實(shí)表明，最佳編程解決方案應(yīng)利用通用算法形式的可互換標(biāo)準(zhǔn)容器。可以根據(jù)容器的類型，迭代器和支持算法對其進(jìn)行參數(shù)化。

Voronoi圖的每個(gè)變體都有特定的要求，這些要求決定了實(shí)現(xiàn)的簡便性。討論的Voronoi圖的簡單變體在網(wǎng)站如何存儲在集合中以及如何訪問它們方面有所不同。

由于要求極少，Voronoi圖的蠻力變型特別有吸引力。此變體對容器中數(shù)據(jù)的存儲方式?jīng)]有任何限制。它只要求容器提供對每個(gè)元素的訪問。在C ++ 11中，任何提供正向迭代器的標(biāo)準(zhǔn)容器都滿足這些要求。因此，下列所有的容器都適合Voronoi圖的蠻力變體：set，unordered_set，vector，deque，list和forward_list。

基于倒排列表的Voronoi圖的表示形式顯得微不足道。此變型具有以下要求。它假定一個(gè)代表一組Voronoi站點(diǎn)的容器以字典順序或排序順序存儲數(shù)據(jù)。容器必須提供一種有效的算法來查找站點(diǎn)集中的初始搜索位置，并且必須支持向前和向后順序搜索。

當(dāng)性能很重要時(shí)，與蠻力版本相比，合適的STL容器的種類大大減少了。這是為什么特定的STL容器不適合實(shí)施Voronoi圖的改進(jìn)變體的一些原因。單鏈接列表（std::forward_list）無法提供對前一個(gè)元素的有效訪問。雙向鏈表（std::list）對于查找初始搜索位置效率不高。基于哈希表（std::unordered_set）的容器不維護(hù)站點(diǎn)的詞典編排或排序順序。

可接受的有效容器的選擇基本上由最近鄰居搜索的第一階段確定，該搜索在有序站點(diǎn)集中找到初始位置。有兩種類型的數(shù)據(jù)結(jié)構(gòu)可有效支持所需的操作。數(shù)組和基于數(shù)組的容器提供二進(jìn)制搜索，運(yùn)行時(shí)間為對數(shù)。在C ++標(biāo)準(zhǔn)庫中，這種類型的最合適的容器是std::vector。庫函數(shù)std::lower_bound()使用隨機(jī)訪問迭代器在有序容器中實(shí)現(xiàn)了對初始位置的有效搜索。平衡的搜索樹可以獲得相同的對數(shù)運(yùn)行時(shí)間。所述std::set容器通常是基于一個(gè)紅黑樹和支持通過成員函數(shù)所需要的搜索std::set::lower_bound()。

在C ++中，std::vector它是默認(rèn)的標(biāo)準(zhǔn)容器，因?yàn)樗鼮樵S多類型的應(yīng)用程序提供了最佳性能。但是，對于需要對Voronoi圖進(jìn)行頻繁更新操作的用戶算法而言，它并不總是最佳選擇。由于插入和擦除操作的線性運(yùn)行時(shí)間，此類算法的性能可能會大大下降，這比最近鄰居搜索的平方根運(yùn)行時(shí)間明顯差。std::set提供具有對數(shù)運(yùn)行時(shí)間的更新操作的容器可以提供更好的性能。

在復(fù)雜的用戶算法中，最有效的標(biāo)準(zhǔn)容器的選擇并不明顯。運(yùn)算的計(jì)算成本分析非常困難且無效。使用可互換STL容器的通用算法為調(diào)整性能和選擇容器提供了一種簡單實(shí)用的方法。對每個(gè)可接受容器的用戶算法運(yùn)行時(shí)間的度量使人們能夠找到合適的容器。

鑒于STL僅是一個(gè)通用庫，使用標(biāo)準(zhǔn)容器簡單表示Voronoi圖所提供的功能令人印象深刻。特別有趣的是，基本上免費(fèi)獲得對更新操作的有效支持。使用參數(shù)化解決方案時(shí)，只需std::vector要將模板參數(shù)從更改為即可std::set。這種優(yōu)勢來自關(guān)鍵的設(shè)計(jì)原則，即標(biāo)準(zhǔn)庫提供了各種各樣的可互換容器，這些容器對接口操作具有不同的性能保證。

同時(shí)，使用基本數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)容器不可能在所有類型的應(yīng)用程序中提供最佳性能。例如，STL對要求高效隨機(jī)訪問元素和更新操作的問題的解決方案提供了有限的支持。具有隨機(jī)訪問迭代器的標(biāo)準(zhǔn)容器具有插入和擦除操作的線性運(yùn)行時(shí)間，而具有快速更新操作的容器僅支持雙向迭代器。這些限制可以通過應(yīng)用前面提到的關(guān)鍵STL設(shè)計(jì)原則來解決?？梢酝ㄟ^新的高效數(shù)據(jù)結(jié)構(gòu)來提高算法的性能。在通用算法中，這些數(shù)據(jù)結(jié)構(gòu)應(yīng)用作STL擴(kuò)展，以支持標(biāo)準(zhǔn)容器和迭代器的接口。

Voronoi圖的可視化在實(shí)際應(yīng)用中很重要。盡管所討論的簡單表示不提供單元的邊界，但是它允許人們輕松地在位圖上繪制Voronoi圖。這是Voronoi分配模型的應(yīng)用示例。繪制方法為每個(gè)站點(diǎn)分配唯一的顏色，然后應(yīng)用最近的鄰居搜索算法以設(shè)置每個(gè)像素的顏色。使用此方法已獲得圖1所示的Voronoi圖的圖像。

距離變換[2]與Voronoi圖密切相關(guān)（請參見圖5）。它計(jì)算查詢點(diǎn)與其最近站點(diǎn)之間的距離?？梢酝ㄟ^將距離值映射到用作查詢點(diǎn)的每個(gè)像素的亮度來可視化距離轉(zhuǎn)換。

圖5：圖1和2中使用的同一組點(diǎn)的距離變換。像素的亮度與像素與其最近位置之間的距離的平方成正比。

所討論的Voronoi圖表示的性能已使用模擬距離變換計(jì)算的算法進(jìn)行了測量。與Voronoi圖相比，距離變換的實(shí)現(xiàn)更為簡單，從而說明了這一選擇。該測試將生成一個(gè)隨機(jī)的二維點(diǎn)集，這些二維點(diǎn)代表Voronoi圖的位置并填充指定的矩形。每個(gè)容器按字典順序存儲站點(diǎn)，以確保最近鄰搜索的平方根計(jì)算復(fù)雜性。該測試測量計(jì)算從指定矩形內(nèi)的每個(gè)點(diǎn)到其最近位置的距離所需的總運(yùn)行時(shí)間。

該測試的運(yùn)行時(shí)間表明std::vector具有最佳性能。這是因?yàn)樵撊萜髦性氐倪B續(xù)排列提供了對測試所需元素的快速隨機(jī)和順序訪問。與蠻力算法相比，距離變換的計(jì)算使我們能夠測量有序集合中搜索提供的性能增益。在Windows 7系統(tǒng)上，對于N = 100 ，運(yùn)行時(shí)間縮短2.9倍，對于N = 10,000點(diǎn)，運(yùn)行時(shí)間縮短28倍std::vector。因此，當(dāng)N時(shí)，性能增益將增加約10倍。 增加了100倍。此結(jié)果與這兩種算法的漸近計(jì)算復(fù)雜度得出的平方根估計(jì)一致。

該代碼已為C ++ 03編譯器開發(fā)。在C ++ 11編譯器中，boost::chrono可以替換為std::chrono。

標(biāo)準(zhǔn)序列容器（std::vector，std::list和std::deque）已經(jīng)被包含在示例算法來演示如何處理在通用算法的容器的特定代碼，并允許用戶比較各種數(shù)據(jù)結(jié)構(gòu)的性能。這些容器在修改Voronoi圖的應(yīng)用程序中并不安全。更新操作違反了兩個(gè)不變性：容器中元素的順序和唯一性。可以使用STL擴(kuò)展來解決此問題，例如基于數(shù)組的擴(kuò)展Boost::flat_set，它們支持的接口std::set。這種容器將提高解決方案的安全性，并提供與相同的效率std::vector。

命名空間中的代碼VoronoiDemo通過為二維點(diǎn)的X和Y坐標(biāo)使用精確的整數(shù)類型，避免了與數(shù)字錯(cuò)誤有關(guān)的問題。兩點(diǎn)之間的距離的計(jì)算已被平方距離的計(jì)算所代替，該距離也利用了精確的整數(shù)類型。

用C ++開發(fā)的最近鄰居搜索可為少量代碼帶來相當(dāng)不錯(cuò)的性能提升。這一事實(shí)使該算法與其匹配的C＃實(shí)現(xiàn)進(jìn)行比較很有趣。

將代碼從C ++移植到C＃并不是很困難，但是有一個(gè)微妙的實(shí)現(xiàn)細(xì)節(jié)。C＃算法使用三態(tài)比較，而C ++中的標(biāo)準(zhǔn)算法假定容器數(shù)據(jù)類型支持嚴(yán)格的弱排序（簡單放置，運(yùn)算符較少）。附件中的C＃代碼通過提供與C ++AlgoOrderedList.LowerBound()等效的功能解決了此問題std::lower_bound()。在其他方面，C＃實(shí)現(xiàn)比C ++更簡單。特別是，它沒有在容器的類型上參數(shù)化。它List僅用于編寫，這意味著此演示不直接適合于數(shù)學(xué)集的表示。這個(gè)C＃變體的好處是它允許我們將其運(yùn)行時(shí)間與基于的最快C ++變體進(jìn)行比較std::vector。

C ++和C＃算法已經(jīng)在裝有AMD Ryzen 7 PRO 3700處理器，16GB RAM和Windows 10 Pro操作系統(tǒng)的臺式計(jì)算機(jī)上進(jìn)行了測試。附帶的代碼Stopwatch在C＃和chrono::high_resolution_clockC ++中支持以毫秒為單位的計(jì)算時(shí)間的度量?？蓤?zhí)行代碼是在Visual Studio 2019中使用具有默認(rèn)項(xiàng)目設(shè)置的控制臺應(yīng)用程序生成的。

測試蠻力算法可以確認(rèn)它具有線性計(jì)算復(fù)雜性（請參閱下表）。C ++算法比C＃算法快大約3倍。

C ++ 88 830 8,180

C＃ 270 2,900 28,700

對于基于有序數(shù)據(jù)集搜索的算法（請參見下表），漸近平方根復(fù)雜度達(dá)到N約10,000。

C ++ 22 58 146 430

C＃ 100 240 625 2,040

在此測試中，C ++的優(yōu)勢看起來更加令人印象深刻。它比C＃的性能高出將近5倍。盡管如此，在應(yīng)用程序中選擇此算法的C＃變體無疑是值得的。從比較N > = 1,000的運(yùn)行時(shí)間可以看出，它比蠻力搜索（包括其C ++變體）要快得多。該測試是當(dāng)數(shù)據(jù)集的大小可以增加幾個(gè)數(shù)量級時(shí)應(yīng)避免使用暴力算法的原理的另一說明。

本節(jié)說明了為什么Delaunay三角剖分超出了本文的范圍，以及為什么在本文的第一個(gè)版本中省略了其討論。

一組二維點(diǎn)的三角剖分表示將平面細(xì)分為一組三角形。對于給定的點(diǎn)集，存在許多三角剖分。在某些方面，Delaunay三角剖分是最完美的三角剖分，并且它是Voronoi圖的對偶圖（請參見圖6）。Delaunay三角剖分的頂點(diǎn)對應(yīng)于Voronoi細(xì)胞及其位置。Delaunay三角剖分中的頂點(diǎn)的連通性由Voronoi細(xì)胞的邊界邊緣定義。Delaunay三角剖分具有許多有趣的特性，使其在廣泛的實(shí)際應(yīng)用中有用[3]。

圖6：一組點(diǎn)的Delaunay三角剖分（紅色）和Voronoi圖（灰色單元格邊界）。通過在相鄰Voronoi細(xì)胞的位點(diǎn)之間繪制線段來可視化Delaunay三角剖分。線段不一定與Voronoi單元的相應(yīng)邊界邊緣相交。請注意，三角剖分僅覆蓋輸入點(diǎn)集的凸包內(nèi)部的區(qū)域。

平面細(xì)分的相似性并不意味著對Voronoi圖有效的方法可以直接應(yīng)用于Delaunay三角剖分。在本文的上下文中，Delaunay三角剖分的主要顯著特征是它是平面圖。圖的有效表示需要一個(gè)頂點(diǎn)存儲到相鄰邊的列表。因此，Delaunay三角剖分的復(fù)雜度與Voronoi圖的基于邊界的變體相同?；谝唤M站點(diǎn)和最近鄰居搜索的Voronoi圖的討論的簡單表示不滿足圖形表示的這一要求。Delaunay三角剖分的幾何結(jié)構(gòu)比Voronoi圖更復(fù)雜。