经典问题二
❖ 在一个矩形区域中有n个点，找到一个点，使 得其到所有给定点的距离的最小值最大
经典问题二
❖ 首先，我们想确定区域内的每个点，是到哪个给定 点的距离最近，如果这样分类成功，我们就可以求 出每个给定点的对应区域中离它最远的点，然后求 其中的最大值
❖ 对于一个给定点，其对应区域的所有点必须满足到 其他点的距离比到给定点的距离长
❖ 回忆上学期学过的Delaunay三角剖分，发现 其与Voronoi图有一些共同特点
❖ 都是给定了若干点，然后做一个划分 ❖ Delaunay三角剖分和Voronoi图都是唯一的 ❖ 都包含了某种最优划分的思想
两者的实质关系
❖ Delaunay三角剖分的任意一个三角形的外心 是Voronoi图中的多边形的顶点
❖ Voronoi图中相邻的两个多边形对应的给定点 的连线必然是Delaunay三角剖分中的三角形 边
2008年安全评价人员教育培训
谢谢聆听
❖ 对于只有两个点的情况，这个区域正是两点的中垂 线分割出来的区域，是一个半平面
❖ 那么问题就转化成了半平面求交
Voronoi图
❖ 上题中提到的对于给定点的区域凸多边形划 分，是一个计算几何中的经典模型，被称做 Voronoi图
❖ 半平面求交并不是求Voronoi图的最优算法
联想Delaunay三角剖分
经典问题一
❖ 首先，能够看到所有边的点必然能看到整个 多边形
❖ 假设多边形的顶点按逆时针方向给出 V0V1V2……Vn，V0= Vn。能看到边ViVi+1的点 Qi必然满足QiVi× QiVi+1>=0（指两个向量叉 乘），事实上此时Qi的解集是一个半平面