期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一种Voronoi划分减量构造算法 被引量：2

Decrement construction algorithm for Voronoi tessellation
下载PDF
导出
摘要 减量构造Voronoi划分(DCVT)是利用已有的Voronoi划分,局部重构删除节点后的Voronoi划分。详细分析删除一个节点对其他节点的Voronoi区域的影响,将DCVT的主要工作简化为求解一个简单的有界Voronoi划分;最后,提出一种有界Voronoi划分的求解策略,在此基础上给出DCVT的算法描述。理论分析与实验表明,算法平均时间复杂度为O(1)。 After deleting one node from the given Voronoi tessellation,Decrement Construction Voronoi Tessellation（DCVT） is to locally reconstruct the Voronoi tessellation of the remaining nodes.The changes of other Voronoi regions after deleting one node are analyzed.The main job of DCVT is simplified to construct a bounded Voronoi tessellation.The algorithm of DCVT is proposed based on a simple strategy of building the bounded Voronoi tessellation.Theoretic analysis and experiment results show that the average time complexity of the proposed algorithm is O（1）.
作者 徐鹏飞 陈志刚 刘刚
机构地区 湖南师范大学数学与计算机科学学院 中南大学信息科学与工程学院
出处 《计算机工程与应用》 CSCD 北大核心 2011年第11期7-10,共4页 Computer Engineering and Applications
基金 国家自然科学基金No.60873082 湖南师范大学青年基金项目(No.60901)~~
关键词 VORONOI划分 有界Voronoi划分 减量构造 Voronoi tessellation bounded Voronoi tessellation decrement construction
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献9

  • 1蒋杰,方力,张鹤颖,窦文华.无线传感器网络最小连通覆盖集问题求解算法[J].软件学报,2006,17(2):175-184. 被引量：90
  • 2Zhou Z,Das S R.Variable radii connected sensor cover in sensor networks[J].ACM Transactions on Sensor Networks, 2009,5 ( 1 ) : 387-396.
  • 3Ch T V.Distributed energy-efficient solutions for area coverage problems in wireless sensor networks[D].Atlanta: Georgia State University, 2009: 60-83.
  • 4Wang J, Sirisha M.Energy efficient coverage with variable sensing radii in wireless sensor networks[C]//IEEE International Conf on Wireless and Mobile Computing,Networking and Communications, 2007 : 61-65.
  • 5Zhang C, Zhang Y C.Detecting coverage boundary nodes in wireless sensor networks[C]//IEEE International Conf on Net- works, 2006: 868-873.
  • 6程丹,杨钦,李吉刚,蔡强.二维黎曼流形的Voronoi图生成算法[J].软件学报,2009,20(9):2407-2416. 被引量：5
  • 7Devillers O.On deletion in Delaunay triangulations[C]//15th Annual ACM Symposium on Computational Geometry, 1999: 1.81-188.
  • 8Mostafavi M A,Gold C.Delete and insert operations in voronoi/ delaunay methods and applications[J].Computers & Geosciences, 2003,29(4) :520-523.
  • 9周培德计算几何[M].2版.北京:清华大学出版社,2005:147-160.

二级参考文献19

  • 1Bulusu N,Heidemann J,Estrin D.GPS-Less low cost outdoor localization for very small devices.IEEE Personal Communications Magazine,2000,7(5):28-34.
  • 2He H,Huang C,Blum BM,Stankovic JA,Abdelzaher TF.Range-Free localization schemes in large scale sensor networks.In:Johnson DB,ed.Proc.of the ACM MobiCom 2003.San Diego:ACM Press,2003.81-95.
  • 3Romer K,Zurich E.The lighthouse location system for smart dust.In:Siewiorek D,ed.Proc.of the 1st Int'l Conf.on Mobile Systems,Applications,and Services.San Francisco:ACM Press,2004.15-30.
  • 4Okabe A,Boots B,Sugihara K,Chiu S.Spatial Tessellations:Concepts and Applications of Voronoi Diagram.2nd ed.,New York:John Wiley & Sons,1999.
  • 5Hochbaum DS.Approximation Algorithms for NP-Hard Problems.Cambridge:PWS Publishing Company,1995.
  • 6Cormen TH,Leiserson CE,Rivest RL,Stein C.Introduction to Algorithms.2nd ed.,Cambridge:MIT Press,2001.
  • 7Yah T,He T,Stankovic J.Differentiated surveillance service for sensor networks.In:Akyildiz IF,Estion D,eds.Proc.of the 1st Int'l Conf.on Embedded Networked Sensor Systems.Los Angels:ACM Press,2003.51-63.
  • 8Gupta H,Das SR,GU Q.Connected sensor cover:Self-Organization of sensor networks for efficient query execution.In:Gerla M,ed.Proc.of the ACM MobiHoc 2003.Annapolis:ACM Press,2003.189-200.
  • 9Akyildiz IF,Su W,Sankarasubramaniam Y,Cayirci E.Wireless sensor networks:A survey.Computer Networks,2002,38(4):393-422.
  • 10Elson J,Estrin D.Sensor Networks:A Bridge to the Physical World.Norwell:Kluwer Academic Publishers,2004.3-20.

共引文献93

同被引文献14

引证文献2

二级引证文献6

计算机工程与应用
2011年 第11期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部