钱桥+平面图处理方法

《钱桥+平面图处理方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、平面图的处理方法清华大学钱桥一、平面几何中的基本元素点、向量角度直线、射线、线段简单多边形求向量夹角向量旋转点与线的位置关系点到线的投影线段求交点与简单多边形的位置关系给定一个凸多边形A，查询一个点是否在它内部。——O(n)预处理，O(logn)在线回答给定一个顶点满足极角序的多边形B，查询一个点是否在它内部。——O(n)预处理，O(logn)在线回答给定一个多边形C，查询一个点是否在它内部。给定一个平面图D，查询一个点在哪个域。O(nlogn)预处理，O(logn)回答！这就是我们今天的目标！二、平面图的基本性质定义：若图G可画在平面上，使得任意两条边都不会在非端点处相交，

2、则称G是平面图。n：平面图中的点数m：平面图中的边数k：平面图中连通块的数量r：平面图中域的数量性质1：r=m–n+k+1证明：对于n个点，生成为k个连通块的森林，需要n-k条边在此基础上，保持连通块数量不变，每增加一条边，会导致增加一个域由于初始有1个域，增加的边数为m-(n-k)，故域数为m–n+k+1。性质2：r<=2*n–4性质3：m<=3*n-6证明：每个域最少也要有3条边包围，每条边可用2次，故有2*m>=3*r。带入等式r=m–n+k+1，再结合k>=1即可。结论：平面图中边、域的数量均是O(n)的。三、平面图的存储一个优秀的存储结构应满足：占用空间小构建时间复

3、杂度低支持快速的查询邻接矩阵邻接表占用空间：构建时间：查询相邻边：遍历全图：O(n^2)O(n+m)O(n^2+m)O(n+m)O(n)O(n^2)O(deg(u))O(n+m)平面图需要支持哪些查询操作？对于一个域，查询其周围的点和边为每个域创建一个列表，存储其边界上的点和边（1）对于一个域，查询其相邻的域为平面图创建对偶图（2）对于一个点，查询其相邻的边——邻接表步骤0：化无界为有界步骤1：将每条边拆成两条有向边，需要有指针指向对方步骤2：将每个点发出的有向边按照顺时针排序步骤3：任取一条未访问的边出发，在每个节点处选择顺时针第一条边，直到返回出发的边为止。构建结构（1）

4、：构建结构（2）：记录每条边从属于哪个域为每个域在对偶图中创造一个点为每条边在对偶图中创造一条边对于不连通的图，应如何处理？通过这个算法，无法得到图中的圆环域，也无法得到这个域与中心方块域相邻的关系。对于不连通的图，应如何处理？添加这条边之后：平面图中域的数量不变，即对偶图中点的数量不变。平面图中边的数量增加了，但对应的对偶图中只增加了一个自环。对偶图的应用：平面图最大流平面图最小割对偶图最短路Case1：无向图有向图Case2：Case3：四、梯形图及其查找结构查询一个点在哪个域，在上述的结构（1）、结构（2）中仍然需要O(n)的时间。为了使查询操作更快，我们需要更强大的结

5、构来维护平面图。一种思路是，引入若干条垂直竖线将平面图切割：查询可做到O(logn)构建需要O(n^2*logn)域的数量会增加至O(n^2)尝试改进划分方式另一种思路是，每个点沿竖直方向发出射线，碰到其他点或线段即停止在这个结构中，每个域均是梯形（三角形可看做是退化的梯形）。域的数量是O(n)的。如何证明？基本假设：所有点横坐标互异证明：每个点引出两条射线，至多增加两个节点。故节点总数不超过3*n。除节点处无交点，仍然是平面图。故域的数量仍是O(n)。除了这张梯形图外，我们还需要一个查找结构：五、构造梯形图查找结构——随机增量法思考题：任给平面上n个节点，请在O(n)时间内

6、找到一个尽可能小的圆，使得所有的点都在圆内或圆上将i个点随机排列，则第i个点在前i-1个点的轮廓圆外的概率不大于3/i。已得到前i-1个点的轮廓圆，判断第i个点是否在该圆内：(i-3)/i的概率：在圆内或圆上，可直接忽略该点3/i的概率：在圆外，需要重新构造前i个点的轮廓圆若可在O(i)的时间内为前i个点构造轮廓圆，则可在O(1)时间内，将前i-1个点的轮廓圆扩展为前i个点的轮廓圆任务：在O(n)的时间内，为n个点构造轮廓圆将n个点的顺序随机打乱，时间复杂度O(n)已得到点a与前j-1个点的轮廓圆，判断第j个点是否在该圆内：(j-2)/j的概率：在圆内或圆上，可直接忽略该点2

7、/j的概率：在圆外，需要重新构造前j个点的轮廓圆若可在O(j)的时间内为前j个点与点a构造轮廓圆，则可在O(1)时间内，将点a与前j-1个点的轮廓圆扩展为点a与前j个点的轮廓圆子任务：在O(i)时间内，为前i个点构造轮廓圆。已知其中i号点一定在圆上！称其为点a。将前i-1个点的顺序随机打乱，时间复杂度O(i)子任务：在O(j)时间内，为前j个点构造轮廓圆。已知其中点a与点b（j号点）一定在圆上！一次循环即可搞定！构造梯形图及其查找结构：最初，梯形图中没有任何点和边，只有一个梯形域，对应的查找结构中只有一