Scalable exact visualization of isocontours in road networks via minimum-link paths

DOI10.20382/JOCG.V9I1A2MaRDI QIDQ4626288zbMATH OpenOpenAlexFDO

Authors Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, Franziska Wegner

Publication date 27 February 2019

Full work available at URL https://arxiv.org/abs/1602.01777

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, answering queries in a few milliseconds on average even for long ranges.

Recommendations

• The shortest path problem on large-scale real-road networks
• Fast paths in large-scale dynamic road networks
• Schematization of road networks
• Algorithms – ESA 2005
• Schematization of networks

Cited in

(1)

• Shortcut hulls: vertex-restricted outer simplifications of polygons

This page was built for publication: Scalable exact visualization of isocontours in road networks via minimum-link paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4626288)