Gabriel图

参考https://www.jianshu.com/p/7f27273d5f23?from=timeline
定义:

如果节点u和节点v之间,直径为uv的圆内,不存在其它顶点W,则节点u和节点v存在GG边(u,v)。用方程式表示如下:
Gabriel图
下图形象地说明了RNG平面图的定义,节点u和节点v之间形成一个直径为d(u,v)的圆形,节点u和节点v都在圆上,即是圆形阴影区域。若(u,v)是GG中的边,则在节点U和V之间的圆形阴影区域,不能包含有任何证明节点w。

 

Gabriel图

GG平面图的算法

直径为uv的圆形阴影的圆心也是uv的中点。对于每个节点u,有完整的邻节点列表N,用以下伪代码去除非GG连接:
Gabriel图
从两者的定义可以看出,RNG是GG的子集,差别在GG只是在节点间较小的圆形阴影区域内搜寻证明节点。如下图所示,左图是无线网络的完整拓扑图;200个节点被随机部署在2000*2000米的区域,无线电范围为250米;中间表示整个拓扑图的GG子图;右图表示整个拓扑图的RNG子图。
Gabriel图