平面多边形凹凸性的算法研究

首先介绍目前计算机辅助设计应用系统中判断平面多边形凹凸性的常用算法，鉴于它具有占较多的ＣＰＵ时间、循环复杂、而且次数多，从而提出了一种判断平面多边形凹凸性的新方法，该算法逐点进行凹凸性判断，算法简单，循环少，占用的ＣＰＵ时间也大大减少。该算法对Ｃｏｏｎｓ，Ｂｅｚｉｅｒ，Ｂ－ｓｐｌｉｎｅ样条曲线特征多边形的凹凸性判断具有重要的意义。

平面凸多边形斜支撑线求解的最佳算法

平面凸多边形斜支撑求解是计算几何中诸多问题的一个核心算法．至今，求解该问题的最好算法的时间复杂度为Ｏ（ｎ＋ｍ）．本文在巧妙利用凸多边形特殊性质的基础上，给出了一时间复杂度为Ｏ（ｌｏｇ（ｎ＋ｍ））的最佳算法，从而彻底解决了这一问题．

多根避雷针联合保护的充要条件

在变电所设计中,需要为变电所配置一定数量的避雷针。这些避雷针一般位于一个凸多边形的顶点上。电力部门提供了多根避雷针联合保护的判据如下: 两根避雷针。假定针高为h_1和H_2,两针距离为D,在保护高度h_x上我们计算出值b_x(b_x,是h_1,h_2,D和h_x的函数),若b_x≥0则两根针可以联合保护,保护区域如图1所示。

斯坦纳树和凸多边形的WSN分区双连通恢复

针对无线传感器网络分区在恢复连通后仍然容错不足的问题,提出斯坦纳树和凸多边形的分区双连通恢复方法.首先,以距离为依据选取现有叶子节点来促使少数未连通的离散节点统一成区;然后,将分区抽象成点后枚举出所有的非退化型四边形,进而将计算得到的四边形中的两个斯坦纳点与4个顶点连接构造斯坦纳边部署中继节点,使分区实现单连通;最后,利用格雷厄姆凸壳算法选取抽象点中的凸壳顶点连接,形成凸多边形实现分区的双连通,并对第2轮连通路径上的中继节点实施休眠唤醒机制.在保证关键节点二次失效不会使网络再次瘫痪的基础上,简化网络结构并降低数据通信延迟.通过仿真,将所提出方案与利用最小斯坦纳树优化中继节点布局的分布式算法(DORMS)和1C-SpriderWeb算法进行对比,对比结果表明所提出方案可减少中继节点的部署数量,延长网络寿命.