摘要： 为处理圆柱面和圆锥面上数据集的最近邻查询问题，提出利用Voronoi图进行查询和曲面转换2种解决方法。在圆柱面和锥面上构造Voronoi图，利用Vornoi图进行查询处理。将圆柱面和锥面转换映射为二维有界平面，给出转换规则和查询算法。对2种方法进行实验分析，结果表明，利用Voronoi图的方法适合静态数据集的最近邻查询，曲面转换方法对动态数据集的最近邻查询更有效。
关键词:
最近邻,
反向最近邻,
圆柱面,
圆锥面,
Vornoi图
Abstract: To handle the Nearest Neighbor(NN) query problem on the cylindrical and cone surface effectively, the two methods are proposed. The methods is respectively the method based on the Voronoi diagram and the method of the curve-divert-plane. The Voronoi diagram can be constructed on the cylindrical and cone surface and the query can be done based on the properties of the Voronoi diagram. In the method of curve-divert-plane, the cylindrical and cone surface can be diverted into the 2D plane and the divert-rule, the query algorithm are given. The performances of the two methods are analyzed by experiment. Experimental results show that the method based on the Voronoi diagram can deal with the nearest neighbor query of the static datasets well and the method of the curve-divert-plane can handle the dynamic datasets effectively.
Key words:
Nearest Neighbor(NN),
reverse Nearest Neighbor(NN),
cylindrical surface,
cone surface,
Voronoi diagram
中图分类号:
张丽平, 李松, 郝晓红, 王淼, 蔡志涛. 圆柱面和锥面上数据集的最近邻查询方法[J]. 计算机工程, 2012, 38(2): 29-31.
ZHANG Li-Beng, LI Song, HAO Xiao-Gong, WANG Miao, CA Zhi-Chao. Nearest Neighbor Query Method of Datasets on Cylindrical and Cone Surface[J]. Computer Engineering, 2012, 38(2): 29-31.