将一个平面用 
个点划分为 凸多边形，使得每个 多边形 包含 恰好一个 生成点，并且给定多边形中的每个点都比任何其他生成点更接近其生成点。沃罗诺伊图有时也称为狄利克雷镶嵌。这些单元格称为狄利克雷区域、泰森多边形或 沃罗诺伊多边形。
早在 1644 年，勒内·笛卡尔就考虑过沃罗诺伊图，狄利克雷 (1850) 在研究正定二次型时使用了它。沃罗诺伊 (1907) 也对其进行了研究，他将沃罗诺伊图的研究扩展到更高的维度。它们在计算机图形学、流行病学、地球物理学和气象学等领域得到广泛应用。沃罗诺伊图一个特别值得注意的应用是分析 1854 年伦敦霍乱疫情，当时医生约翰·斯诺确定死亡与靠近宽街上某个（受感染的）水泵之间存在很强的相关性（斯诺 1854，斯诺 1855）。在他的分析中，斯诺绘制了一张地图，并在地图上画了一条标有“宽街水泵与其他水泵之间等距边界”的线。这条线基本上指示了宽街水泵的沃罗诺伊单元（奥斯汀 2006）。然而，对于一篇分析文章，强调了围绕斯诺和伦敦霍乱事件的民间历史叙述中的一些过度简化和错误归因，请参阅 Field (2020)。
Wolfram 语言命令VoronoiDiagram[pts] 在 Wolfram 语言包中ComputationalGeometry`返回与给定点集的沃罗诺伊图对应的数据结构，以及DiagramPlot[pts] 给出沃罗诺伊图的图形说明（上图左侧）。在 Wolfram 语言 中，使用图形函数（例如ListDensityPlot和ListPlot3D以及选项设置InterpolationOrder -> 0（右侧两图）。
德劳内三角剖分和 
中的沃罗诺伊图在图论意义上是对偶的。
在电视罪案剧《数字追凶》第 4 季剧集“黑天鹅”中，数学天才查尔斯·埃普斯提议对重叠的狄利克雷镶嵌进行时间序列分析，以试图追踪嫌疑人的行动轨迹。
另请参阅
美术馆定理,
计算几何,
凸包,
德劳内三角剖分,
半空间交集,
中轴,
三角剖分,
沃罗诺伊多边形
使用 Wolfram|Alpha 探索
参考文献
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.在 Wolfram|Alpha 中被引用
沃罗诺伊图
请按如下方式引用
Weisstein, Eric W. "Voronoi Diagram." 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/VoronoiDiagram.html
主题分类
