这段证明我觉得写得很冗长 没办法很简单的就知道我想要表达甚麽 而且课本上好像没有这个演算法 只有稍微类似的演算法 希望有人可以帮我改的结构和逻辑好一点 附上图之类的 ---------------------- 证明正确性的重点应该是 加入一个新的点之後 那个点会是新的convex hull的成员 而且那个点必须要连到哪个点 时间复杂度的难处是 删除掉的点总共会花多少时间 找出加入的点必须连结到哪个点所花的时间 -------------------- 甚麽是convex hull? 对於点集合Q的最小凸多边形P使Q的成员"不是在P的边上就是在P的里面" 则定义为CH(Q) 解决的方法 递回的演算法 做法 1 找出点集合Q中最左边的点L 2 点p属於{点集合Q中除了L的点} 3 依照线段(p,L)的斜率由小到大排序 4 形成点集合P={p2,p3,p4,.......,pn} 5 定义CHi(P)是点L和点p2到点pi形成的convex hull 6 令CH3(P)={L,P2,P3} 7 for i = 4 to n 8 let 点r1= L 9 let 点r2= 点r1沿着CHi边顺时针方向下一点 10 do theta=向量(r1-pi)和向量(rj-r2)的夹角 11 while theta>180度 12 let 点r1= r2 13 let 点r2= 点r1沿着CH(i-1)(P)边顺时针方向下一点 14 do theta=向量(r1-pi)和向量(rj-r2)的夹角 15 do CHi(P)= CH(i-1)(P)-(L沿着CHi的边顺时针走到r1所经过的所有点)+ pi 16 输出CHn(P) 正确性 1.CH3(P)={L,P2,P3} 因为三个点才能形成凸包,所以CH3的成员一定会包含L,p2,p3 2.pi属於CHi(P) 因为CHi(P)上的边(L,pi)比边(L,p'),p'是p2,p3,......,p(i-1)任何一点斜率都大 所以pi属於CHi,否则其他的边无法把pi包住 3.r2属於CHi(P) 因为r2是第一个令theta<=180度的点 又因为CH(i-1)(P)是convex hull所以每个边的夹角都<=180度 所以所有的点都会在线段(pi,r2)的同一边 因此r2属於CHi(P) 时间复杂度 line 1 花O(n) line 3 排序会花O(n*log(n)) line 6 O(1) line 7~15 每一次找CHi(P)需要加入一个点,花O(1) 删去被原本是CH(i-1)(P)包住的点,因为每一点最多只能被删去一次,所以是O(n) 找出r2要花的时间和删去被原本是CH(i-1)(P)包住的点时间一样,是O(n) 总和是O(n*log(n)) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 58.114.209.65 ※ 编辑: ajnightmare 来自: 58.114.209.65 (05/10 00:38) ※ 编辑: ajnightmare 来自: 58.114.208.7 (06/19 00:51)