computational_geometry(方灿).ppt

1、Computational Geometry: Voronoi Diagram and Delaunay Triangulation,2011 by Fang, Can,1,Post Office: What is the area of service?,Definition of Voronoi Diagram,Let P be a set of n distinct points (sites) in the plane. The Voronoi diagram of P is the subdivision of the plane into n cells, one for each

2、 site. A point q lies in the cell corresponding to a site pi P iff Euclidean_Distance( q, pi ) Euclidean_distance( q, pj ), for each pi P, j i.,Voronoi Diagram Example:1 site,Two sites form a perpendicular bisector,Voronoi Diagram is a linethat extends infinitely in both directions, and thetwo half

3、planes on eitherside.,Collinear sites form a series of parallel lines,Non-collinear sites form Voronoi half lines that meet at a vertex,Half lines,A vertex hasdegree 3,Voronoi Cells and Segments,Voronoi Cells and Segments,Existence of Bounded Cells,Which of the following is true for2-D Voronoi diagr

4、ams? Four or more non-collinear sites are sufficient to create a bounded cell necessary to create a bounded cell 1 and 2 none of above,Existence of Bounded Cells,Which of the following is true for2-D Voronoi diagrams? Four or more non-collinear sites are sufficient to create a bounded cell necessary

5、 to create a bounded cell 1 and 2 none of above,Degenerate Case: no bounded cells!,v,Voronoi Properties,A point q lies on a Voronoi edge between sites pi and pj iff the largest empty circle centered at q touches only pi and pj A Voronoi edge is a subset of locus of points equidistant from pi and pj,

6、e : Voronoi edge,v,v : Voronoi vertex,pi,pi : site points,Voronoi Properties,A point q is a vertex iff the largest empty circle centered at q touches at least 3 sites A Voronoi vertex is an intersection of 3 more segments, each equidistant from a pair of sites,e : Voronoi edge,v,v : Voronoi vertex,p

7、i,pi : site points,Voronoi Properties,2011 by Fang, Can,15,Property 3. Empty circle property This inscribed circle is empty, i.e. it does not contain any other sites Property 4. Nearest-neighbor property If Q is the nearest neighbor of P then their Voronoi regions share an edge (to find a nearest ne

8、ighbor it is sufficient to check only neighbors in the VD) Property 5. Voronoi region Vor(P) is unbounded if and only if P belongs to the boundary of convex hull of S.,Voronoi diagrams have linear complexity |v|, |e| = O(n),Intuition: Not all bisectors are Voronoi edges!,e,e : Voronoi edge,pi,pi : s

9、ite points,Voronoi diagrams have linear complexity |v|, |e| = O(n),Claim: For n 3, |v| 2n 5 and |e| 3n 6 Proof: (Easy Case),Collinear sites |v| = 0, |e| = n 1,Voronoi diagrams have linear complexity |v|, |e| = O(n),Claim: For n 3, |v| 2n 5 and |e| 3n 6 Proof: (General Case) Eulers Formula: for conne

10、cted, planar graphs,|v| |e| + f = 2 Where: |v| is the number of vertices |e| is the number of edges f is the number of faces,Voronoi diagrams have linear complexity |v|, |e| = O(n),Claim: For n 3, |v| 2n 5 and |e| 3n 6 Proof: (General Case) For Voronoi graphs, f = n (|v| +1) |e| + n = 2,e,pi,p,To ap

11、ply Eulers Formula, we “planarize” the Voronoi diagram by connecting half lines to an extra vertex.,Voronoi diagrams have linear complexity |v|, |e| = O(n),Moreover, and so together with we get, for n 3,Constructing Voronoi Diagrams,Half plane intersection O( n2 log n ) Fortunes Algorithm Sweep line

12、 algorithm O( n log n ),Delaunay triangulation,Definition 3. A Delaunay triangulation (DT) is the straight-line dual of the Voronoi diagram obtained by joining all pairs of sites whose Voronoi regions share a common Voronoi edge Follows from the definition: If two Voronoi regions Vor(P) and Vor(Q) s

13、hare an edge, then sites P and Q are connected by an edge in the Delaunay triangulation If a Voronoi vertex belongs to Vor(P), Vor(Q) and Vor(R), then DT contains a triangle (P,Q,R),Delaunay triangulation,DT properties,Assumption 2. No three points from the set S lie on the same straight line. Theor

14、em. The straight-line dual of the Voronoi diagram is a triangulation of S Property 1. The circumcircle of any Delaunay triangle does not contain any points of S in its interior Property 2. If each triangle of a triangulation of the convex hull of S satisfies the empty circle property, then this tria

15、ngulation is the Delaunay triangulation of S,VD and DT,VD and DT,Both DT and VD effectively represent the proximity information for the set of sites. They can be easily transformed into each other. VD contains geometrical information, while DT contains topological information.,Generalized Voronoi di

16、agram,Given a set S of n sites (spheres) in d-dimensional space Distance function d(x,P) between a point x and a site P is defined.,Generalized Voronoi diagram,A generalized Voronoi diagram (GVD) for a set of objects in space is the set of generalized Voronoi regions where d(x,P) is a distance funct

17、ion between a point x and a site P in the d-dimensional space.,Generalized Delaunay tessellation,A generalized Delaunay triangulation (GDT) is the dual of the generalized Voronoi diagram obtained by joining all pairs of sites whose Voronoi regions share a common Voronoi edge.,General metrics,General

18、ized distance functions Power Additively weighted Euclidean Manhattan supremum,Voronoi图的在信息学中的应用,例3.Fat Man,例1.Run Away,例2.Voronoi图与平面MST问题,Voronoi图的在信息学中的应用,例1.Run Away 平面上有一个矩形，在矩形内有一些点，请你求得矩形内另一个点，该点离与它最近的已知点最远（点的个数=1000）。,B,A,C,D,Voronoi图的在信息学中的应用,思路一：容易想到用枚举法,情况一：过三点的圆的圆心,情况二：两点中垂线与矩形的边的交点,B,A,

19、所求点,C,B,A,C,所求点,D,D,Voronoi图的在信息学中的应用,根据刚才分析的两种情况，我们可以构造两种方案。第一种方案针对所求点为过三个点的圆的圆心的状态，我们枚举三个点，求出它们组成的三角形的外心和半径，然后枚举其它的点，看它们是不是在这个圆中。第二种方案是枚举两个点的中垂线，求出中垂线与矩形的交点，然后根据这三个点来计算最远位置，进行判断。,它的时间复杂度：O(n4),Voronoi图的在信息学中的应用,思路二：Voronoi图,首先介绍一个Voronoi图的性质：设v是Vor(S)的顶点，则圆C(v)内不含S的其他点。根据这个性质我们很容易想到用Voronoi图来解决问题，

20、方法如下：,步1.计算点集S的Voronoi图Vor(S)。,步2.计算点集S的凸壳CH(S)。设得到的圆最大半径Rmax =0。,步3.枚举每个Voronoi点v,如果v在矩形内部，计算v为圆心的圆的半径并且修改Rmax 。,步4.枚举枚个CH(S)中的边e，求出e的中垂线与矩形的交点v，计算v到边e两端点的距离，并且修改Rmax。,时间复杂度 O(n log n),Voronoi图与平面MST问题,例2.平面MST问题 给定平面上的点集S，求出连接S中所有点的最小长度的树，并且要求最小生成树的结点恰好是S中的点。,Voronoi图与平面MST问题,传统的求最小生成树的方法是贪心法，要是纯粹

21、使用贪心法求平面最小生成树，我们所作的程序时间复杂度至少为：O(n2),有没有更快的方法呢？,Voronoi图与平面MST问题,我们都知道Voronoi图的对偶图是点集的角Delaunay Triangulation，我们把这个三角剖分中的边组成的集合叫做DT(S). 那么，我们可以得出这样一个定理：,最小生成树MST是角最优三角剖分DT(S)的一个子集,关于定理的证明,也就是说，具有直径ab的圆周上或圆内必有S中的点，假设c在该圆周上或者圆内，那么|ac|ab|，并且|bc|ab|。那么，我们删除ab，把树T分成Ta和Tb两部分，不妨假设cTa，那么我们添加边cb，可以合并成新的树，并且的总

22、长度小于T，因此包含ab的树长度不可能是最小的。所以必然MSTDT(S),证明： 假设存在一条边abDT(S)，则由三角剖分的定理可以知道过a,b有一个空圆。因此如果ab不属于DT(S)，那么过a,b的圆不可能是空的。,a,b,c,Ta,Tb,Voronoi图与平面MST问题,根据这个条件，我们可以得到一个新的方案，构造角最优三角剖分，然后计算最小生成树，总的时间复杂度是O(n log n)。,Voronoi图拓宽解题思路,例3.Fat Man 在超市走廊上两边都是墙，中间有一些障碍物，这些障碍物都是一些很小的半径可以忽略的点，你是一个胖子，可以将你的抽象成一个圆柱。现在你要从走廊的一头走到另

23、一头。请问你最大的直径是多少？（走廊长L,宽W）,问题分析：,刚开始拿到题目可能会手足无措，如果只是知道平面上的一些点，我们很难确定从走廊一头到另一头的路线，也很难运用枚举等方法来解决问题。但是，当你学了Voronoi图，情况就不一样了！,Voronoi图拓宽解题思路,首先我们建立Voronoi图，显然一个人如果想穿过这些障碍物，那么走Voronoi边才是最佳的，因为如果不走Voronoi边，必然会使你的圆心进入一个Voronoi多边形内，这将使人更靠近一个障碍物，因而会减少人的半径。所以最佳路线必定由一些Voronoi边组成。,原来障碍点,Voronoi图拓宽解题思路,接下来，由于人还可以从

24、走廊边与障碍物之间通过，那么对于每一个障碍点(x,y)我们可以在走廊壁上增加障碍点(x,0),(x,W),一共增加2n个障碍点。另外在走廊开始和尽头增加四个障碍点（-W,0），（-W,W），（L+W,0），（L+W,W）这四个点与其它点之间距离不小与W，这样就不影响结果。然后对于这3n+4个点求Voronoi图。,最后我们对于整个图进行变相的求最短路即可。,新增点,原来障碍点,总结,距离问题,减少冗余计算,特殊几何问题,带来新思路,运用Voronoi图,运用Voronoi图,O(n4),O(n log n),O(n2),O(n log n),没思路,有思路,从无到有,化繁为简,扩展思路,45,

25、Worst and Best-Case Coveragein Sensor Networks,Seapahn Meguerdichian , Farinaz Koushanfar , Miodrag Potkonjak , Mani Srivastava,IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL.4, NO. 1, JANUARY-FEBRUARY 2005 IEEE Infocom 2001, Vol. 3, pp. 1380-1387, April 2001.,46,Outlines,Introduction Sensing models and

26、 assumptions Coverage formulations Maximal Breach Maximal Support Experimental Conclusion,47,Coverage,Coverage can be considered as a measure of the quality of service of a sensor network. Coverage formulations can try to find weak points in a sensor field suggest future deployment or reconfiguratio

27、n schemes for improving the overall quality of service.,48,Coverage Problem,Given: Field A S sensors, specified by coordinates Initial(I) and final(F) locations of an agent (I , F) How well can the field be observed ? Worst Case Coverage: Find a maximal breach path for an agent moving in A. Best Cas

28、e Coverage: Find a maximal support path for an agent moving in A.,49,Worst Case Coverage,We want to find the closest distance to sensors that an agent traveling on any path in the sensor field must encounter at least once. We determine the closest distance to sensors even if the agent tries to optim

29、ally avoid the sensors.,50,Best Case Coverage,We want to find the farthest distance to sensors that an agent traveling on any path in the sensor field must have from sensors, even if it tries to stay as close to sensors as possible. At some points, the agent must move away from sensors in order to b

30、e able to traverse the field.,51,Key Highlight,Transform the difficult to represent coverage problems to discrete-domain optimization using computational geometry and graph theory constructs: Voronoi Diagram Delaunay Triangulation,52,Sensing Model,We express the general sensing model S at an arbitra

31、ry point p for a sensor s as:,where d(s,p) is the Euclidean distance between the sensor s and the point p, and positive constants and K are sensor technology dependent parameters,53,Assumption,Sensing effectiveness diminishes as distance increases Homogeneous sensor nodes Sensor node locations are k

32、nown Non-directional sensing technology Centralized computation model,54,Coverage Formulation,How well can the field be observed ? Worst Case Coverage: Maximal Breach Path Best Case Coverage: Maximal Support Path The “paths” are generally not unique. They quantify the best and worst case observabili

33、ty (coverage) in the sensor field.,55,Maximal Breach Path,Given: Field A instrumented with sensors S; areas I and F. Breach: the minimum Euclidean distance from P to any sensor in S. Problem: Identify PB, the Maximal Breach Path in S, starting in I and ending in F. PB is defined as a path with the p

34、roperty that for any point p on the path PB, the distance from p to the closest sensor is maximized.,56,Enabling Step: Voronoi Diagram,By construction, each line-segment maximizes distance from the nearest point (sensor). Consequence: Path of Maximal Breach of Surveillance in the sensor field lies o

35、n the Voronoi diagram lines.,57,58,59,Graph-Theoretic Formulation,Given: Voronoi diagram D with vertex set V and line segment set L and sensors S Construct graph G(N,E): Each vertex viV corresponds to a node ni N Each line segment li L corresponds to an edge ei E Each edge eiE, Weight(ei) = Distance

36、 of li from closest sensor sk S Formulation: Is there a path from I to F which uses no edge of weight less than K?,60,Finding Maximal Breach Path,Algorithm Generate Voronoi Diagram Apply Graph-Theoretic Abstraction Search for PB Check existence of path I - F using BFS Search for path with maximal, m

37、inimum edge weights This is a Maximal Breach Path, PB, and it is not unique.,61,62,Critical Regions,30 sensors are deployed at random.,63,Bounded Voronoi Diagram,Sensor field with Voronoi Diagram and a Maximal Breach Path.,64,Maximal Support Path,Given: Field A instrumented with sensors S; areas I a

38、nd F. Support : the maximum Euclidean distance from the path P to the closest sensor in S. . Problem: Identify Ps, the Maximal Support Path in S, starting in I and ending in F. Only requirement: the distance from the farthest point on Ps to the closest sensor is minimized.,65,Maximal Support Path,Gi

39、ven: Delaunay Triangulation of the sensor nodes Construct graph G(N,E): The graph is dual to the Voronoi graph previously described Formulation: what is the path from which the agent can best be observed while moving from I to F? (The path is embedded in the Delaunay graph of the sensors) Solution:

40、Similar to the max breach algorithm, use BFS and Binary Search to find the shortest path on the Delaunay graph.,Sensor field with Delaunay triangulation and a Maximal Support Path (Ps),66,Maximal Breach Path Example (50 nodes),67,Maximal Breach Path Example (200 nodes),68,Maximal Breach Path Sensor

41、Deployment,Even after deploying 100 sensors, breach coverage can be improved by about 10 percent by deploying just one more sensor.,69,Maximal Support Path Sensor Deployment,70,Asymptotic Behavior,On average, after deploying about 100 sensors, additional random sensors do not improve coverage very significantly.,71,Conclusions,Best and Worst case coverage formulations Efficient optimal algorithms using computational geometry and graph theory Maximal Breach