Extracting a transit geopoint set from routing API

Abstract

In the paper we deal with the data describing road routes between many to many geographical points (geopoints) provided by a black box for routing. The black box takes two geographical points as an input, and outputs the travel time/distance of a route and the array of manoeuvre points. A single call of the black box incurs unit cost. Linear growth in the number of geographical points thus leads to the quadratic growth of costs. We propose a method for extracting a transit point set. The set is then used for determining suboptimal routes while generating nearly linear costs. We show experimentally that suboptimal routes do not deviate significantly from originally generated routes.