Voronoi 划分把空间按「谁最近」切给一组种子点：每个种子统治一块最近邻区域。最近邻查询、矢量量化、K-means 的决策结构在几何上都是它。
定义
给定 维空间中的点集 （种子，seeds/sites），每个 归属离它最近的种子：
称胞腔（cell），全体胞腔构成对空间的 Voronoi 划分。欧氏度量下每个不等式 化简后是一个半空间，胞腔 = 半空间之交，必为凸多面体；边界点同时满足多个不等式，归属不唯一，实现时任取其一即可。
关键性质
- Delaunay 对偶：连接所有相邻胞腔的种子得到 Delaunay 三角剖分；Voronoi 顶点对应 Delaunay 三角形的外接圆圆心（空圆性质）。
- 度量无关：定义对任意距离度量成立。换成马氏距离 ，胞腔变成「斜」的加权结构——正是 VQ 加权 MSE 度量码本的几何形态（见 马氏距离）。
- 唯一性由 tie-breaking 保证：种子共圆/共球时边界退化，需要固定决胜规则，否则数值实现里同一点会漂移到不同胞腔。
左：8 个种子的胞腔，深色边界即「距离相等」的中垂线段。右：同一组种子的 Delaunay 三角剖分，虚线外接圆内不含其他种子——空圆性质的直接图示，两图互为对偶。
在量化与聚类中的角色
VQ 的最近邻条件——给定码本，输入归入最近码矢的胞腔——在几何上就是以码矢为种子做 Voronoi 划分：量化 = 定位所在胞腔，输出其种子。LBG/K-means 的 E 步逐样本做这件事，M 步把种子挪到胞腔质心，收敛后的聚类结果就是一张以质心为种子的 Voronoi 图。kNN 分类器同构：训练点为种子，新样本落进谁的胞腔就按谁投票。完整链条见 矢量量化（VQ）：从码本设计到率失真理论。
点的颜色 = 所属胞腔，灰线连向其码矢——最近邻条件的直接图示，胞腔边界即量化器的决策边界。
构造与计算
| 场景 | 方法 | 复杂度 |
|---|---|---|
| 二维平面 | Fortune 扫描线 | |
| 一般维度（显式构造） | 半空间交 / 凸包对偶 | ，随维度指数恶化 |
| 只需逐点归属 | 暴力最近邻 / KD 树 | 每查询 ；高维 KD 树退化到暴力 |
三维的胞腔是凸多面体（外围远点把无限区域压成有界多面体以便渲染）。维度继续升高，显式构造与渲染都指数退化——正是下面维度诅咒的几何形态。
高维下显式构造不可行——这正是 VQ 码本搜索 瓶颈的几何根源，也是 乘积量化（PQ）：高维向量检索的工程基石 的动机：用笛卡尔积把一张大 Voronoi 图拆成多张小图的叠加。
Python 实现
import numpy as np
from scipy.spatial import Voronoi
seeds = np.random.default_rng(0).normal(size=(8, 2))
vor = Voronoi(seeds) # 显式构造：vor.vertices / vor.regions 拿胞腔顶点（低维适用）
def locate(x, seeds):
"""逐点归属：量化 / kNN 实际用的形态——最近邻的编号即胞腔编号。"""
return np.argmin(((seeds - x) ** 2).sum(axis=1))