关键词: 线段Voronoi图，空间数据库，线段最近对，线段最小距离

Abstract: Closest pair(CP) query is one of the important spatial queries in spatial database. But the existed researches on CP query are mainly focused on point objects,which can rarely solve some instance that spatial object can not be abstracted as a point. The question of closest pair query between line segment and line segment was first put forward.That is finding the line segment pair which has the shortest distance among all the line segment pairs of two line segment sets. The line segment closest pair ctuery algorithm based on Voronoi diagram was proposed, and the relevant theorern and proof were given. `hhe Voronoi diagram of two line segment sets was constructed respectively in the method. By making use of nearest adjacent property and local dynamic property, the line segment pairs that arc the nearest neighbor mutually were finded from which the result was got, in order to reduce a lot of computational cost. The two circumstances of insert line segment and delete line segment were dealed with. Experiments demonstrate the proposed algorithms have high query efficiency.

Key words: Line segment Voronoi diagram, Spatial database, Line segment closest pair, Line segment nearest distance