將一個平面用 
個點劃分為 凸多邊形，使得每個 多邊形 包含 恰好一個 生成點，並且給定多邊形中的每個點都比任何其他生成點更接近其生成點。沃羅諾伊圖有時也稱為狄利克雷鑲嵌。這些單元格稱為狄利克雷區域、泰森多邊形或 沃羅諾伊多邊形。
早在 1644 年，勒內·笛卡爾就考慮過沃羅諾伊圖，狄利克雷 (1850) 在研究正定二次型時使用了它。沃羅諾伊 (1907) 也對其進行了研究，他將沃羅諾伊圖的研究擴充套件到更高的維度。它們在計算機圖形學、流行病學、地球物理學和氣象學等領域得到廣泛應用。沃羅諾伊圖一個特別值得注意的應用是分析 1854 年倫敦霍亂疫情，當時醫生約翰·斯諾確定死亡與靠近寬街上某個（受感染的）水泵之間存在很強的相關性（斯諾 1854，斯諾 1855）。在他的分析中，斯諾繪製了一張地圖，並在地圖上畫了一條標有“寬街水泵與其他水泵之間等距邊界”的線。這條線基本上指示了寬街水泵的沃羅諾伊單元（奧斯汀 2006）。然而，對於一篇分析文章，強調了圍繞斯諾和倫敦霍亂事件的民間歷史敘述中的一些過度簡化和錯誤歸因，請參閱 Field (2020)。
Wolfram 語言命令VoronoiDiagram[pts] 在 Wolfram 語言包中ComputationalGeometry`返回與給定點集的沃羅諾伊圖對應的資料結構，以及DiagramPlot[pts] 給出沃羅諾伊圖的圖形說明（上圖左側）。在 Wolfram 語言 中，使用圖形函式（例如ListDensityPlot和ListPlot3D以及選項設定InterpolationOrder -> 0（右側兩圖）。
德勞內三角剖分和 
中的沃羅諾伊圖在圖論意義上是對偶的。
在電視罪案劇《數字追兇》第 4 季劇集“黑天鵝”中，數學天才查爾斯·埃普斯提議對重疊的狄利克雷鑲嵌進行時間序列分析，以試圖追蹤嫌疑人的行動軌跡。
另請參閱
美術館定理,
計算幾何,
凸包,
德勞內三角剖分,
半空間交集,
中軸,
三角剖分,
沃羅諾伊多邊形
使用 探索
參考文獻
Aurenhammer, F. 和 Klein, R. "Voronoi Diagrams." Ch. 5 in Handbook of Computational Geometry (Ed. J.-R. Sack 和 J. Urrutia). Amsterdam, Netherlands: North-Holland, pp. 201-290, 2000.Austin, D. "Voronoi Diagrams and a Day at the Beach." Aug. 2006. http://www.ams.org/publicoutreach/feature-column/fcarc-voronoi.Barber, C. B.; Dobkin, D. P.; 和 Huhdanpaa, H. T. "The Quickhull Algorithm for Convex Hulls." ACM Trans. Mathematical Software 22, 469-483, 1996.de Berg, M.; van Kreveld, M.; Overmans, M.; 和 Schwarzkopf, O. "Voronoi Diagrams: The Post Office Problem." Ch. 7 in Computational Geometry: Algorithms and Applications, 2nd rev. ed. Berlin: Springer-Verlag, pp. 147-163, 2000.Dirichlet, G. L. "Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen." J. reine angew. Math. 40, 209-227, 1850.Eppstein, D. "Nearest Neighbors and Voronoi Diagrams." http://www.ics.uci.edu/~eppstein/junkyard/nn.html.Field, K. "Something in the Water: The Mythology of Snow's Map of Cholera." Dec. 3, 2020. https://www.esri.com/arcgis-blog/products/arcgis-pro/mapping/something-in-the-water-the-mythology-of-snows-map-of-cholera/.The Geometry Center. "Qhull." http://www.qhull.org/.Guibas, L. 和 Stolfi, J. "Primitives for the Manipulation of General Subdivisions and the Computations of Voronoi Diagrams." ACM Trans. Graphics 4, 74-123, 1985.Klee, V. "On the Complexity of 
-Dimensional Voronoi Diagrams." Archiv. Math. 34, 75-80, 1980.Okabe, A.; Boots, B.; 和 Sugihara, K. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd ed. New York: Wiley, 2000.Preparata, F. R. 和 Shamos, M. I. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.Skiena, S. S. "Voronoi Diagrams." §8.6.4 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 358-360, 1997.Snow, J. On the Mode of Communication of Cholera. London: C. F. Cheffins, 1854.Snow, J. On the Mode of Communication of Cholera, 2nd ed. London: Churchill, 1855. http://www.ph.ucla.edu/epi/snow/snowbook.html.Snow, J. "John Snow's Map 1 (1854)." In On the Mode of Communication of Cholera. London: Churchill, 1855. http://www.ph.ucla.edu/epi/snow/snowmap1_1854_lge.htm.Voronoi, G. "Nouvelles applications des paramètres continus à la théorie des formes quadratiques." J. reine angew. Math. 133, 97-178, 1907.在 中被引用
沃羅諾伊圖
請按如下方式引用
Weisstein, Eric W. "Voronoi Diagram." 來自 網路資源。 https://mathworld.tw/VoronoiDiagram.html
主題分類
