利用紧凑Voronoi图计算非支配点

### 利用紧凑 Voronoi 图计算非支配点 在许多实际应用中，如多目标优化、数据挖掘等，常常需要找出数据集中的非支配点（也称为天际线点）。本文将介绍如何利用紧凑 Voronoi 图来计算非支配点，主要涉及非支配点与 Voronoi 图的关系、相关概念的定义以及具体的计算算法。 #### 非支配点与 Voronoi 图的基本关系 首先给出一个重要结果：集合 P 相对于站点集合 S 的非支配点，是在由 S 确定的凸距离函数和由 P 确定的加法权重下，具有非空 Voronoi 单元的点。下面详细解释这个关系。 选择 S 的凸包内的一个原点，对于集合 P 中的每个点，我们可以构建对应的锥体。具体步骤如下： 1. 考虑一个顶点在原点的单位抛物面。 2. 对于集合 P 中的点 p，将其提升到单位抛物面上得到点 p'。 3. 对于凸包 CH(S) 中的每个站点 s，考虑以 s 为中心且经过 p 的圆盘。将这些圆盘提升到单位抛物面上，形成经过 p' 的平面。所有这些平面的提升版本形成一个顶点在 p' 的锥体。这样，集合 P 中的 n 个点就对应 n 个锥体。 4. 这些锥体的下包络的顶点对应于非支配点或天际线点。 这个方案也可以在 Voronoi 图模型中进行解释。将集合 P 中各点的提升坐标作为它们的加法权重。以相同的原点和单位抛物面，将集合 S 中的每个站点提升到与单位抛物面相切的平面。将这些平面平移以包含原点，并相交它们的半空间来定义一个锥体。该锥体在原点垂直上方单位距离处的横截面定义了一个凸多边形，我们用这个凸多边形来定义一个凸距离函数。因此，凸距离函数由集合 S 确定。顶点在集合 P 提升点处的锥体的下包络界定了非支配（加法加权）点，并且可以解释为该凸距离函数的加法加权 Voronoi 图。 #### 支配点与锥体 为了更好地理解非支配点，我们先引入支配点和支配区域的概念。 设 C(x, y) 表示以 x 为中心、半径等于 d(x, y) 的圆盘。对于集合 P 中的每个点 pi，考虑以集合 S 中的每个 sk 为中心的圆盘 C(sk, pi)。显然，对于圆盘 C(sk, pi) 内的任何点 p，sk 到 p 的距离比到 pi 的距离更近。因此，如果点 pj 支配 pi，则 pj 属于所有这些圆盘的交集，即 pj ∈ ∩_{k = 1}^mC(sk, pi)。我们将 Di = ∩_{k = 1}^mC(sk, pi) 称为 pi 的支配区域。支配区域的意义在于，属于 Di 的任何点相对于集合 S 都支配 pi。 对于集合 P 中的任何点 pi，有以下观察结果： 1. **Di 非空且可能与其他 Dj 重叠（j ≠ i）**：这是因为不同点的支配区域可能存在交集。 2. **Di 是由圆弧界定的凸区域**：由于圆盘的交集性质，支配区域必然是凸的，且边界由圆弧组成。 3. **如果 pi 的支配区域 Di 内部不包含集合 P 中其他点 pj（j ≠ i），则 pi 是天际线点**：这是天际线点的一个重要判定条件。 4. **如果点 pj 属于区域 Di（i ≠ j），则 pj 的支配区域 Dj 是 Di 的子集，即 Dj ⊂ Di**：可以通过反证法证明。假设 Di 不包含 Dj，那么存在一个点 z ∈ Dj 但 z ∉ Di，使得 z 支配 pj 但不支配 pi。但由于 pj 支配 pi，且支配关系是传递的，这就产生了矛盾。 通过抛物面变换，我们可以将二维平面中的支配区域 Di 映射到三维空间中顶点在 p' 的锥体 Ωi。具体来说，Di = ∩_{k = 1}^mC(sk, pi)，每个 C(sk, pi) 经过抛物面变换后成为经过 p' 的平面 C'(sk, pi)。这些平面的上半空间的交集定义了三维空间中顶点在 p' 的锥体 Ωi，该锥体对应于平面中的支配区域。 如果点 pj 支配 pi，那么对应于 pj 支配区域 Dj 的锥体 Ωj 包含对应于 pi 支配区域 Di 的锥体 Ωi。这是因为在平移过程中，对应于站点的切平面会先包含 pj 的提升点 pj'，再包含 pi 的提升点 pi'。由此可以得出，三维空间中对应于被支配点 pi 的锥体 Ωi 至少会被一个锥体 Ωj 包含。因此，锥体集合 {Ω1, …, Ωn} 的下包络的顶点就是集合 P 的非支配点或天际线点。 #### 锥体下包络与加法加权 Voronoi 图的关系 为了计算非支配点，我们需要进一步探讨锥体下包络与加法加权 Voronoi 图的关系。首先，定义两个重要概念：凸距离函数和加法加权 Voronoi 图。 - **凸距离函数**：Minkowski 证明，任何内部包含原点的凸集 M 都定义了一个凸距离函数 dM(p, q)，其中从点 p 到点 q 相对于 M 的距离是 M 必须缩放的量，以使 q - p 包含在缩放后的 M 中，即 dM(p, q) = inf{λ ≥ 0 : q - p ∈ λM}。如果 M 是封闭的，则下确界操作可以替换为最小值操作。凸距离函数不一定是度量，因为 dM 对称当且仅当 M 是中心对称的。但 dM 总是满足点的三角不等式：dM(p, q) + dM(q, r) ≥ dM(p, r)。M 的边界作为该距离函数的单位球。对于固定的 p，dM(p, q) 作为 q 的函数的图像是一个顶点在 p 的锥体。 - **加法加权 Voronoi 图**：给定有限点集 P = {p1, p2, …, pn} ⊂ IR^d，具有加法权重 ω1, ω2, …, ωn，以及任何距离函数 d(p, q)，我们可以通过为每个站点 q ∈ IR^d 标记其最近点集来定义广义 Voronoi 图：label(q) = arg min_i∈[1,n] d(pi, q) + ωi，并将平面划分为具有相同标签的最大连通区域。Voronoi 单元是具有单个最近邻的区域，顶点的度数为 d + 1（在退化情况下可能更大）。 有一个重要观察：如果增加站点的权重，该站点的单元会缩小，实际上是将锥体向上平移，直到提升后的站点从下包络中消