Context-dependent Route Generation Scheme Using Network Voronoi Diagrams

Researches on computing an optimal route according to user´s preference or spatial contexts have been gaining focus recently, as car navigation and pedestrian navigation systems are getting accustomed to be used in daily lives. In this paper, the authors propose a method to compute a path to pass through as many context areas as possible along its route, according to the user´s needs. Specifically, the authors apply the concept to construct a Delaunay diagram from neighbor nodes in Voronoi diagram, and use network Voronoi diagram to construct a subgraph based on contexts. For route search, the authors use A* shortest path algorithm over the subgraph. To verify the efficiency of the proposed method with subgraphs, the authors perform route search over subgraphs and base graph, which was generated from the road network of the real space, and compare the results. The results show that the route search by the proposed method consist of more paths with context areas than those performed over the base graph. Moreover, the proposed method reduces the number of steps for path search.