Additively Weighted Voronoi Diagrams for Optimal Sequenced Route Queries

3rd STDBM Workshop on Spatio-Temporal Database Management

Mehdi Sharifzadeh ; Cyrus Shahabi

Others  :  http://CEUR-WS.org/Vol-174/paper5.pdf
PID  :  12062

来源: CEUR

【 摘 要 】

The Optimal Sequenced Route (OSR) query strives to find a route of minimum length starting from a given source location and passing through a number of typed locations in a specific sequence imposed on the types of the locations. In this paper, we propose a precomputation approach to OSR query in vector spaces. We exploit the geometric properties of the solution space and theoretically prove its relation to Additively Weighted Voronoi dia- grams. Our approach recursively accesses these diagrams to incrementally build the optimal se- quenced route. Our experimental results verify that our pre-computation approach outperforms the previous index-based approaches in