蛋白质组学北京大学人工智能实验室ProteomicsArtificialIntelligenceLa.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,半平面求交及相关,吴斌星,线性规划,这个大家都知道,其实线性规划就是半平面求交,由n个形如ax+by+c=0的不等式确定的半平面，求其交集区域,容易知道该区域是至多n边的,凸,多边形,当然前提是在一个有限范围内，如果题目要求无限范围，你只要自己定一个足够大的有限范围即可,朴素算法,初始设区域A为整个平面,一次用给定不等式对应的直线切割A,所有直线切割完毕后得到最终的交集,复杂度O(n,2,),如果要求每增加一个不等式都要输出一次A，该算法是最优的,分治算法,如果可以在O(n+m)的时间里求出一个n条边的凸多边形和一个m条边的凸多边形的交集，那么就可以吧半平面求交的问题分治为两个相当的小问题，然后再合并结果,那么时间复杂度变为O(nlogn),两个凸多边形的交,如右图所示，过凸多边形的顶点做平行于y轴的直线，这些直线将整个平面分成若干个区域，在每个区域里，都是两个梯形（或退化的梯形）求交，只需用时O(1),经典问题一,首先，能够看到所有边的点必然能看到整个多边形,假设多边形的顶点按逆时针方向给出V,0,V,1,V,2,V,n,，V,0,=V,n,。能看到边V,i,V,i+1,的点Q,i,必然满足Q,i,V,i,Q,i,V,i+1,=0（指两个向量叉乘），事实上此时Q,i,的解集是一个半平面,问题转化为这些半平面的交是否为空,经典问题二,在一个矩形区域中有n个点，找到一个点，使得其到所有给定点的距离的最小值最大,经典问题二,首先，我们想确定区域内的每个点，是到哪个给定点的距离最近，如果这样分类成功，我们就可以求出每个给定点的对应区域中离它最远的点，然后求其中的最大值,对于一个给定点，其对应区域的所有点必须满足到其他点的距离比到给定点的距离长,对于只有两个点的情况，这个区域正是两点的中垂线分割出来的区域，是一个半平面,那么问题就转化成了半平面求交,Voronoi,图,上题中提到的对于给定点的区域凸多边形划分，是一个计算几何中的经典模型，被称做Voronoi,图,半平面求交并不是求,Voronoi,图的最优算法,联想Delaunay,三角剖分,回忆上学期学过的Delaunay,三角剖分，发现其与,Voronoi,图有一些共同特点,都是给定了若干点，然后做一个划分,Delaunay,三角剖分和,Voronoi,图都是唯一的,都包含了某种最优划分的思想,两者的实质关系,Delaunay,三角剖分的任意一个三角形的外心是,Voronoi,图中的多边形的顶点,Voronoi,图中相邻的两个多边形对应的给定点的连线必然是,Delaunay,三角剖分中的三角形边,谢谢大家,