《蛋白质组学北京大学人工智能实验室ProteomicsArtificialIntelligenceLaboratoryofPekingUniversity.ppt》由会员分享，可在线阅读，更多相关《蛋白质组学北京大学人工智能实验室ProteomicsArtificialIntelligenceLaboratoryofPekingUniversity.ppt（14页珍藏版）》请在三一文库上搜索。
1、半平面求交及相关,吴斌星,线性规划,这个大家都知道 其实线性规划就是半平面求交 由n个形如ax+by+c=0的不等式确定的半平面，求其交集区域 容易知道该区域是至多n边的凸多边形 当然前提是在一个有限范围内，如果题目要求无限范围，你只要自己定一个足够大的有限范围即可,朴素算法,初始设区域A为整个平面 一次用给定不等式对应的直线切割A 所有直线切割完毕后得到最终的交集 复杂度O(n2) 如果要求每增加一个不等式都要输出一次A，该算法是最优的,分治算法,如果可以在O(n+m)的时间里求出一个n条边的凸多边形和一个m条边的凸多边形的交集，那么就可以吧半平面求交的问题分治为两个相当的小问题，然后再合并
2、结果 那么时间复杂度变为O(nlogn),两个凸多边形的交,如右图所示，过凸多边形的顶点做平行于y轴的直线，这些直线将整个平面分成若干个区域，在每个区域里，都是两个梯形（或退化的梯形）求交，只需用时O(1),两个凸多边形的交,根据这个思想，我们分别求出凸多边形的上方边界和下方边界，合起来就是一个凸多边形 由于最多分成n+m个区域，所以求这些梯形的交用时O(n+m) 在求顶点的x坐标顺序时，可以使用归并排序的思想，用时O(n+m) 总用时O(n+m),经典问题一,已知一个多边形 求其中是否存在一个点，能看到整个多边形,经典问题一,首先，能够看到所有边的点必然能看到整个多边形 假设多边形的顶点按逆
3、时针方向给出V0V1V2Vn，V0= Vn。能看到边ViVi+1的点Qi必然满足QiVi QiVi+1=0（指两个向量叉乘），事实上此时Qi的解集是一个半平面 问题转化为这些半平面的交是否为空,经典问题二,在一个矩形区域中有n个点，找到一个点，使得其到所有给定点的距离的最小值最大,经典问题二,首先，我们想确定区域内的每个点，是到哪个给定点的距离最近，如果这样分类成功，我们就可以求出每个给定点的对应区域中离它最远的点，然后求其中的最大值 对于一个给定点，其对应区域的所有点必须满足到其他点的距离比到给定点的距离长 对于只有两个点的情况，这个区域正是两点的中垂线分割出来的区域，是一个半平面 那么问题
4、就转化成了半平面求交,Voronoi图,上题中提到的对于给定点的区域凸多边形划分，是一个计算几何中的经典模型，被称做Voronoi图 半平面求交并不是求Voronoi图的最优算法,联想Delaunay三角剖分,回忆上学期学过的Delaunay三角剖分，发现其与Voronoi图有一些共同特点 都是给定了若干点，然后做一个划分 Delaunay三角剖分和Voronoi图都是唯一的 都包含了某种最优划分的思想,两者的实质关系,Delaunay三角剖分的任意一个三角形的外心是Voronoi图中的多边形的顶点 Voronoi图中相邻的两个多边形对应的给定点的连线必然是Delaunay三角剖分中的三角形边,谢谢大家,