Efficiently navigating a random Delaunay triangulation
Efficiently navigating a random Delaunay triangulation
复制标题
高效导航随机 Delaunay 三角剖分
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Ross Hemsley
中科院分区：
文献类型：
--
作者：
N. Broutin;O. Devillers;Ross Hemsley
平面图导航是一个重要的问题，对几何数据结构中的点定位和网络中的路由都有重要意义。然而，虽然已经提出了一些算法和存在性证明，但很少有分析可用于生成的路径的属性以及在输入的随机分布假设下生成它们所需的计算资源。本文分析了一种新的确定性的平面导航算法，该算法具有恒定的生成比（相对于欧氏距离），它遵循Delaunay三角剖分中的顶点邻接关系。我们称之为圆锥行走策略。本文证明了在单位面积光滑凸区域上给定n个一致点，对任意起始点z和查询点q，对z和q的锥行走至多可达O（|ZQ| n+ log 7 n）复杂度为O（|ZQ| nloglogn+ log 7 n），随着n趋于无穷大，概率趋于1。我们还证明了在这个模型中，锥行走是（log 3 + n）-无记忆的，对于域中的任何一对起始点和查询点，对于任何正的n，都有很高的概率。我们在整个过程中特别小心，以确保我们的边界是有效的，即使查询点任意接近边界。© 2016 Wiley Periodicals，Inc.随机结构算法，49，95-136，2016年
Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant spanning ratio (w.r.t the Euclidean distance) which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove that given n uniform points in a smooth convex domain of unit area, and for any start point z and query point q; cone walk applied to z and q will access at most O(|zq|n+log7n) sites with complexity O(|zq|nloglogn+log7n) with probability tending to 1 as n goes to infinity. We additionally show that in this model, cone walk is (log3+ξn) ‐memoryless with high probability for any pair of start and query point in the domain, for any positive ξ. We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 95–136, 2016
无线传感器网络
DOI：
10.1007/978-3-642-11917-0_10
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Cheng L
通讯作者：
Cheng L