论文--计算几何中的二分思想.doc

计算几何中的二分思想【摘要】本文简要阐述了计算几何中的二分思想,并通过例题对其进行应用,体现二分在计算几何中简洁高效的优势。【关键字】计算几何二分【引言】二分思想,古已有之,邵子曰:“一分为二,二分为四,四分为八也。”正是根据这样的思想,我们的祖先创造了太极八卦。在当今的信息时代中,这一古老的智慧依旧闪耀着光芒,通过渗透到各门新兴学科中发扬光大,计算几何学就是其中之一。在此基础上,产生了无数经典算法,例如用分治法求解最近点对、凸包、三角剖分和空间分区二叉树。在近年来的各类信息学竞赛中,不断涌现了大批关于计算几何的试题,其中许多复杂的题目可以利用二分思想得到简单解决。掌握了这一思想,无疑是多了一把解决相关问题的利器。【例题解析】下面,就让我们通过几个例题,一起探究二分思想的应用。例题一、work(2005ACM/ICPCWorldFinals)题意:已知B(1≤B≤50)个信号站和C(1≤C≤50)座城市的坐标,坐标的绝对值不大于1000,每个城市使用最近的信号站。给定R(1≤R≤250)条连接城市线路的描述和Q(1≤Q≤10)个查询,求相应两城市间通信时最少需要转换信号站的次数。分析:显然,题目要求的是最短路,关键在于线路权值的计算。题目中告诉我们:每个城市使用最近的信号站,也就是说,该城市所处位置位于平面中离这一信号站最近的点的轨迹内,而离各点最近点的轨迹就是Voronoi图。因此,每条路线的权值就是这条线段所穿过的Voronoi边的数量。由上可看出,题目即为求Voronoi图与最短路的简单组合,只需分别解决。通过以上的分析,我们发现了一种最直接的办法:先求Voronoi图,再求最短路。此法时间效率也足以通过测试,可是求Voronoi图的编程复杂度很高、调试麻烦,在真实的竞赛环境中实用性不强。有没有更好一点的解法呢?考虑一条线段l,如果l两端点所属的信号站相同,显然l的权值为零,否则将l从中点(红点)分为两部分(分割点不在Voronoi边上)l1和l2,l所对应的权值自然就等于l1和l2的权值之和。然后,对l1和l2进行同样的操作。由于不可能无限的分割下去,当两端点的距离小于某个设定的小正常数e(实验证明e∈[10-10,10-5]均能AC),并且与两端点所属信号站不同(蓝点),两点之间就一定存在一条Voronoi边与线段相交,该段权值为一。利用上述办法,可以在不作Voronoi图的情况下,简单地求出各边的权值,避免了冗长的代码;之后使用Floyd或Dijkstra等最短路算法,问题即可完整解决。小结:计算几何有许多诸如Voronoi图的经典模型,在方便思考的同时,也会让我们陷入固有的思维定势,难以自拔。当原有的模型不能方便地解决问题时,就需要另辟蹊径,跳出传统思维来考虑问题。在本例中,通过二分思想,将一条线段分为两半,利用分治法解出问题,使题目化繁为简,易于编程,避开了求作Voronoi图的套路。例题二、CollectingLuggage(2007ACM/ICPCWorldFinals)题意:已知一简单N(3≤N≤100)边形的各顶点坐标,行李箱从第一个顶点以速度Vl沿多边形边界移动,人从点(px,py)出发,速度为Vp(0<Vl<Vp≤10000,单位为米每分),所有坐标均为绝对值不大于10000的整数(单位为米),求人最快取得行李的时间(精确