基于线性四叉树结构的Voronoi图反向膨胀生成方法

摘要：

提出一种基于线性四又树结构并顾及矢量与栅格计算性质的Voronoi图生成方法,其核心思想是利用线性四叉树结构以减小空间割分所产生的空间复杂度,改变膨胀模拟操作的计算方向以减小时间复杂度.讨论了基于数学形态学的反向膨胀计算模型及推理出基于该计算模型的几个优化计算性质.实验验证,这种方法能够有效地平衡时空复杂度,并且易于求取邻元,其时间复杂度小于均匀格网结构与常规四叉树结构.一般情况下,空间复杂度小于均匀格网结构.

关键词：Voronoi图、反向膨胀、线性四叉树结构、计算模型、空间索引

所属期刊栏目：37

分类号：P208(一般性问题)

资助基金：国家自然科学基金40337055;40301042

在线出版日期：2008-07-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：236-242