5.1 应用预览
(Applications: Preview)
- 消防瞭望塔 Fire Observation Towers:
想象一片广阔的森林，里面矗立着若干座消防瞭望塔。如果发生了森林火灾，那么距离火灾最近的瞭望塔上的护林员就需要负责扑灭它。 某位特定护林员负责的所有树木的集合，就构成了与她那座瞭望塔相关联的"维诺多边形 Voronoi Polygon"。 而维诺图则描绘出了这些责任区域之间的分界线，也就是森林中与两座或更多座瞭望塔距离相等的地点。参考图 5.5 可能有助于直观理解。 图5.5太糊了，这里不贴了，下一节再说吧。 - 燃烧的瞭望塔 Towers on fire:
现在，请想象这样一个奇特的情境，所有的护林员同时点燃了他们的瞭望塔，而森林以均匀的速率燃烧。火焰将以每个瞭望塔为中心呈圆形向外蔓延。 那些因为烧到了此前已被焚毁的树木而熄灭的地点，正是与两个或更多瞭望塔距离相等的点，这些点恰好就位于维诺图上。 - 最近邻聚类 Nearest Neighbor Clustering:
在模式识别领域中，通常会将物体描述为特征向量，从而把一组目标物体映射到特征空间中。
第4.6.1节中提到的五个裁缝测量数据的例子，就可以看作是在定义了这样一个特征空间。
对于一个未知归属的物体，其身份可以被判定为特征空间中与其距离最近的目标物体。
举个例子会让这更清晰。假设一个零件箱里包含两种螺母 A 和 B，A 的内径和外径分别为2厘米和3厘米，而B的分别为3厘米和4厘米。特征空间就是二维欧几里得平面的第一象限， 之所以是正值区域，是因为半径不可能为负数。A映射到点\((2, 3)\)，B映射到点\((3, 4)\)。
假设一个视觉系统聚焦于箱子里的一个螺母 \(x\)，并测得其内径和外径分别为 2.8 和 3.7 厘米。考虑到存在测量误差，且箱子里只有A类和B类螺母，那么 \(x\)属于哪种螺母呢? 它极有可能是一颗 B 类螺母，因为它在特征空间中与 B 的距离是 0.36，而与 A 的距离是 1.06。参见图5.1。换句话说，\(x\) 的最近邻是B，因为\(x\)位于B的维诺多边形内。
如果有许多种类型的螺母，识别任务就是在目标螺母的维诺图中定位未知螺母 \(x\)。关于如何高效地实现这一点，将在第5.5.1节中进行讨论。 - 设施选址 Facility Location:
如果你想在已有几家相互竞争的杂货店的区域开设一家新的杂货店。假设人口密度均匀，那么新店应该开在哪里才能使其销售额达到最优？ 满足这一模糊约束的一个自然方法是，将新店选址在距离旧店尽可能远的地方。更准确地说，我们可以选择一个位置，使其与最近的商店的距离最大化。 这等同于将新店选址在"最大空圆(largest empty circle)"的圆心处，即内部不包含其他商店的最大圆的圆心。此时，到最近商店的距离即为该圆的半径。
我们将在第5.5.3节中证明，最大空圆的圆心必然位于维诺图上。 - 路径规划 Path Planning:
想象一个杂乱的环境中，机器人必须规划出一条路径。为了最大限度地降低碰撞风险，机器人希望尽可能远离所有障碍物。 如果我们将问题限定在二维空间，并且假设机器人是圆形的，那么机器人应始终保持在障碍物的维诺图上。 如果障碍物是点(例如细杆)，那么这就是传统的维诺图。如果障碍物是多边形或其他形状，那么需要用到点维诺图的广义版本。
我们将在第8章（第8.5.2节）中重新探讨这个例子。 - 晶体学 Crystallography:
假设有若干个晶种以均匀、恒定的速率生长。当生长不再可能时，晶体将呈现什么样的外观？显然，这与森林大火的情形是类似的，每个晶种将生长成一个维诺多边形，相邻的晶种区域沿着维诺图相接。 维诺图长期以来一直被用于模拟晶体生长。
在模式识别领域中，通常会将物体描述为特征向量，从而把一组目标物体映射到特征空间中。
应用清单可以一直列下去，我们将在第5.5节中看到更多例子。但现在是时候正式定义这个图了。