Reverse nearest neighbor query based on Voronoi diagram and delaunay graph

doi:10.3778/j.issn.1002-8331.2009.18.048

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (18): 162-163.DOI: 10.3778/j.issn.1002-8331.2009.18.048

• 数据库、信息处理 • Previous Articles Next Articles

Reverse nearest neighbor query based on Voronoi diagram and delaunay graph

ZHANG Jia-jia,LIU Run-tao,LI Yang

1.College of Applied Science，Harbin University of Science and Technology，Harbin 150080，China
2.Institution of Information and Scientific Computing Technology，Harbin University of Science and Technology，Harbin 150080，China

Received:2008-04-07 Revised:2008-07-09 Online:2009-06-21 Published:2009-06-21
Contact: ZHANG Jia-jia

基于Voronoi图及其对偶图的反最近邻查询

张佳佳,刘润涛,李杨

1.哈尔滨理工大学应用科学学院，哈尔滨 150080
2.哈尔滨理工大学信息与计算科学研究所，哈尔滨 150080

通讯作者: 张佳佳

Abstract

Abstract: Nearest neighbor query is very common in geographic information system，and based on it，reverse nearest neighbor query is proposed.On the basis of the nearest neighbor query based on Voronoi diagram，the reverse nearest neighbor query based on Voronoi diagram and Delaunay graph is proposed.And the range of the reverse nearest neighbor query is reduced in the large spatial data sets in this method.

Key words: Voronoi diagram, nearest neighbor query, reverse nearest neighbor query

摘要： 最近邻查询是地理信息系统领域经常遇到的问题，而反最近邻查询是在最近邻查询的基础上提出的一种新的查询类型。在分析利用Voronoi图进行最近邻查询的基础上，提出了基于Voronoi图及其对偶图Delaunay图的反最近邻查询，大大缩小了在海量空间数据库中进行反最近邻查询的查询范围。

关键词: Voronoi图, 最近邻, 反最近邻

ZHANG Jia-jia,LIU Run-tao,LI Yang. Reverse nearest neighbor query based on Voronoi diagram and delaunay graph[J]. Computer Engineering and Applications, 2009, 45(18): 162-163.

张佳佳,刘润涛,李杨. 基于Voronoi图及其对偶图的反最近邻查询[J]. 计算机工程与应用, 2009, 45(18): 162-163.

[1]	ZHU Jie1, LU Yi2, ZHANG Huiming1. Path replanning for UAV in emergent threats [J]. Computer Engineering and Applications, 2018, 54(8): 255-259.
[2]	ZHOU Yi1, YANG Zexue1，2. Research on line segment kNN query in spatial database [J]. Computer Engineering and Applications, 2015, 51(18): 131-134.
[3]	XU Ming, CAO Han, TANG Duoyu. Generation and application of weighted Voronoi diagrams for polygons based on Hadoop [J]. Computer Engineering and Applications, 2015, 51(13): 59-62.
[4]	ZHANG Liping1, LI Song1, HAO Xiaohong2, HAO Zhongxiao1. Simple continues near neighbor chain query with increase and decrease of obstacles [J]. Computer Engineering and Applications, 2015, 51(11): 99-103.
[5]	YU Jing, CAO Han, JIN Pengfei. Matrix iteration based parallel algorithm of k-order Voronoi diagram [J]. Computer Engineering and Applications, 2014, 50(6): 102-105.
[6]	HUA Binjie, LIN Lizhong, CHAI Zhongliang. Research on discrete generation algorithm of Voronoi diagram based rough area [J]. Computer Engineering and Applications, 2013, 49(23): 191-194.
[7]	WU Bo1，2, WEN Yuanqiao1，2, XIAO Changshi1，2. Design and simulation of inland maritime unmanned surface vessel path-planning algorithm [J]. Computer Engineering and Applications, 2013, 49(14): 241-246.
[8]	ZHANG Yibin1, WU Gang1, PENG Wenxiu2, CHEN Yanru3. Generation of Voronoi diagram of different traffic network speed [J]. Computer Engineering and Applications, 2012, 48(36): 181-185.
[9]	ZHANG Debin¹，CAO Lijun²，LIANG Yongxin¹，ZHANG Zhongping¹. X*tree index structure for k nearest neighbor queries [J]. Computer Engineering and Applications, 2011, 47(5): 123-125.
[10]	ZHANG Liping，LI Song，HAO Zhongxiao. Research of methods for nearest neighbor query on spherical surface [J]. Computer Engineering and Applications, 2011, 47(5): 126-129.
[11]	LI Jin，YU Jianqiao. Research on technology of reverse nearest neighbor query for spatial objects [J]. Computer Engineering and Applications, 2011, 47(33): 146-148.
[12]	FENG Hong-kui¹，BAO Jin-song^1，2，JIN Ye^1，2. Generalized Voronoi diagrams for multiple robots motion planning [J]. Computer Engineering and Applications, 2010, 46(22): 1-3.
[13]	LAN Lian-yi¹，ZHANG You-hui²，YANG Yu-ping³. Crystal growth of city Voronoi diagram with general transportation networks [J]. Computer Engineering and Applications, 2010, 46(10): 216-219.
[14]	KANG Le. Study on three-dimension path planning for unmanned aircraft vehicle [J]. Computer Engineering and Applications, 2009, 45(33): 236-239.
[15]	ZHANG Li-ping¹，LI Song²，LIU Wen-qiang³，WANG Hong¹. New methods of strong neighborhood pair query [J]. Computer Engineering and Applications, 2009, 45(27): 123-126.

Reverse nearest neighbor query based on Voronoi diagram and delaunay graph

基于Voronoi图及其对偶图的反最近邻查询

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics