用Θ(t)的广义连接图求有障碍时的最短路径

在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题，连接图是研究此问题的基本工具，现有算法构造的最好的连接图GF是基于自由区的概念而设计的，其顶数和边数分别为O（t)和O（tologt)，其中t为障碍的极边数，提出了广义自由区和极大正规划分的概念，在此基础上得到广义连接图GG，用来表征广义自由区之间的邻接情况，其顶数和边数均为Θ（t)，且具有平面图的性质，同时还提出了基于扫描线的极大正规划分构造算法，其时间复杂度为O(tlogt)；并提出规范路径的概念；以及采用“不改向”启发式策略的A^*算法在广义连接图GG中寻找两点间的最短路径，算法的时间复杂度由于GF的现有算法的O(tlogt)降低到Θ（t)。     

Manhattan空间有障碍的最短路径和3-Steiner树算法

在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有(θ)(t).     

Double Barrier Coverage in Dense Sensor Networks

When a sensor network is deployed to detect objects penetrating a protected region, it is not necessary to have every point in the deployment region covered by a sensor. It is enough if the penetrating objects are detected at some point in their trajectory. If a sensor network guarantees that every penetrating object will be detected by two distinct sensors at the same time somewhere in this area, we say that the network provides double barrier coverage （DBC）. In this paper, we propose a new planar structure of Sparse Delaunay Triangulation （SparseDT）, and prove some elaborate attributes of it. We develop theoretical foundations for double barrier coverage, and propose efficient algorithms with NS2 simulator using which one can activate the necessary sensors to guarantee double barrier coverage while the other sensors go to sleep. The upper and lower bounds of number of active nodes are determined, and we show that high-speed target will be detected efficiently with this configuration.     

用（）(t)的广义连接图求有障碍时的最短路径

在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图GF是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图GG,用来表征广义自由区之间的邻接情况,其顶数和边数均为()(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用"不改向"启发式策略的A*算法在广义连接图GG中寻找两点间的最短路径,算法的时间复杂度由基于GF的现有算法的O(tlogt)降低到()(t).