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

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