| 基于Voronoi图的线段反向最近邻查询 |
| |
| 引用本文： | 杨泽雪,郝忠孝.基于Voronoi图的线段反向最近邻查询[J].计算机工程,2011,37(16):30-32. |
| |
| 作者姓名： | 杨泽雪 郝忠孝 |
| |
| 作者单位： | 1. 哈尔滨理工大学计算机科学与技术学院,哈尔滨150080; 黑龙扛工程学院计算机科学与技术系,哈尔滨150050
2. 哈尔滨理工大学计算机科学与技术学院,哈尔滨150080; 哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 |
| |
| 基金项目： | 黑龙江省自然科学基金资助项目，教育部青年基金资助项目 |
| |
| 摘 要： | 提出一种基于平面线段的反向最近邻查询方法，用于找出线段集中以查询线段作为最近邻的线段。通过构造线段集的Voronoi图处理不相交的线段。根据其邻接特性和局部特性，给出基于Voronoi图的线段反向最近邻查询算法及相关定理和证明。实验结果表明，反向最近邻方法易于找到相交的线段，具有较高的查询效率。
|
| 关 键 词： | 平面线段 Voronoi图 线段反向最近邻 空间数据库 查询区域 |
| 收稿时间： | 2010-12-10 |
Line Reverse Nearest Neighbor Query Based on Voronoi Diagram |
| |
| YANG Ze-xue,HAO Zhong-xiao.Line Reverse Nearest Neighbor Query Based on Voronoi Diagram[J].Computer Engineering,2011,37(16):30-32. |
| |
| Authors: | YANG Ze-xue HAO Zhong-xiao |
| |
| Affiliation: | 1,3(1.College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China;2.Department of Computer Science and Technology,Heilongjiang Institute of Technology,Harbin 150050,China;3.College of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China) |
| |
| Abstract: | Reverse Nearest Neighbor（RNN） query between line is put forward.That is finding the line segments that have query line segment as one of their nearest neighbors.According to whether two line segments are intersected,it has two categories： intersected line segment and no intersected.For the former,the reverse nearest neighbor is easy to find.For the latter,by constructing the Voronoi diagram of line segment sets,using the adjacent property and the local property,the line segment RNN query based on Voronoi diagram algorithm is proposed,and the relevant theorem and proof are given.Experimental results demonstrate the proposed algorithms have high query efficiency. |
| |
| Keywords: | plane line segment Voronoi graph Line Reverse Nearest Neighbor（LRNN） spatial database query region |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
