Fast Exact Computation of Isocontours in Road Networks
Moritz Baum, Valentin Buchhold, Julian Dibbelt, Dorothea Wagner · ACM Journal of Experimental Algorithmics · 2019
We study the problem of computing isocontours in static and dynamic road networks, where the objective is to identify the boundary of the region that is reachable from a given source within a certain amount of time (or another limited resource). Although there is a wide range of practical applications for this problem (e.g., urban planning, geomarketing, visualizing the cruising range of a vehicle), there has been little research on fast algorithms for large, realistic inputs, and existing approaches tend to compute more information than necessary. Our contribution is twofold: (1) We propose compact but sufficient definitions of isocontours, based on which (2) we provide several easy-to-parallelize, scalable algorithmic approaches for faster computation. By extensive experimental analysis, we demonstrate that our techniques enable interactive isocontour computation within milliseconds even on continental networks, significantly faster than the state of the art.