Document Open Access Logo

Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.7.pdf
  • Filesize: 2.02 MB
  • 18 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner. Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.7

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 isocontours represented by 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 run in (almost) linear time and 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, computing near-optimal solutions in a few milliseconds on average, even for long ranges.

Subject Classification

Keywords
  • isocontours
  • separating polygons
  • minimum-link paths

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route Planning in Transportation Networks. Technical Report abs/1504.05140, ArXiv e-prints, 2015. Google Scholar
  2. Veronika Bauer, Johann Gamper, Roberto Loperfido, Sylvia Profanter, Stefan Putzer, and Igor Timko. Computing Isochrones in Multi-Modal, Schedule-Based Transport Networks. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'08), pages 78:1-78:2. ACM, 2008. Google Scholar
  3. Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner. Scalable Isocontour Visualization in Road Networks via Minimum-Link Paths. Technical Report abs/1602.01777, ArXiv e-prints, 2016. Google Scholar
  4. Moritz Baum, Valentin Buchhold, Julian Dibbelt, and Dorothea Wagner. Fast Exact Computation of Isochrones in Road Networks. In Proceedings of the 15th International Symposium on Experimental Algorithms (SEA'16), volume 9685 of Lecture Notes in Computer Science, pages 17-32. Springer, 2016. Google Scholar
  5. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Energy-Optimal Routes for Electric Vehicles. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'13), pages 54-63. ACM, 2013. Google Scholar
  6. John L. Bentley and Thomas A. Ottmann. Algorithms for Reporting and Counting Geometric Intersections. IEEE Transactions on Computers, 28(9):643-647, 1979. Google Scholar
  7. Francisc Bungiu, Michael Hemmer, John E. Hershberger, Kan Huang, and Alexander Kröller. Efficient Computation of Visibility Polygons. In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG'14), 2014. Google Scholar
  8. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1):269-271, 1959. Google Scholar
  9. Alexandros Efentakis, Sotiris Brakatsoulas, Nikos Grivas, Giorgos Lamprianidis, Kostas Patroumpas, and Dieter Pfoser. Towards a Flexible and Scalable Fleet Management Service. In Proceedings of the 6th ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWTCS'13), pages 79-84. ACM, 2013. Google Scholar
  10. Alexandros Efentakis, Nikos Grivas, George Lamprianidis, Georg Magenschab, and Dieter Pfoser. Isochrones, Traffic and DEMOgraphics. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'13), pages 548-551. ACM, 2013. Google Scholar
  11. Alexandros Efentakis and Dieter Pfoser. GRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem. In Proceedings of the 22nd Annual European Symposium on Algorithms (ESA'14), volume 8737 of Lecture Notes in Computer Science, pages 358-370. Springer, 2014. Google Scholar
  12. Johann Gamper, Michael Böhlen, and Markus Innerebner. Scalable Computation of Isochrones with Network Expiration. In Proceedings of the 24th International Conference on Scientific and Statistical Database Management (SSDBM'12), volume 7338 of Lecture Notes in Computer Science, pages 526-543. Springer, 2012. Google Scholar
  13. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., 1979. Google Scholar
  14. Ronald L. Graham. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters, 1(4):132-133, 1972. Google Scholar
  15. Leonidas J. Guibas and John E. Hershberger. Optimal Shortest Path Queries in a Simple Polygon. Journal of Computer and System Sciences, 39(2):126-152, 1989. Google Scholar
  16. Leonidas J. Guibas, John E. Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons. Algorithmica, 2(1):209-233, 1987. Google Scholar
  17. Leonidas J. Guibas, John E. Hershberger, Joseph S. B. Mitchell, and J. S. Snoeyink. Approximating Polygons and Subdivisions with Minimum-Link Paths. International Journal of Computational Geometry &Applications, 3(4):383-415, 1993. Google Scholar
  18. Stefan Hausberger, Martin Rexeis, Michael Zallinger, and Raphael Luz. Emission Factors from the Model PHEM for the HBEFA Version 3. Technical Report I-20/2009, University of Technology, Graz, 2009. Google Scholar
  19. Hiroshi Imai and Masao Iri. An Optimal Algorithm for Approximating a Piecewise Linear Function. Journal of Information Processing, 9(3):159-162, 1987. Google Scholar
  20. Markus Innerebner, Michael Böhlen, and Johann Gamper. ISOGA: A System for Geographical Reachability Analysis. In Proceedings of the 12th International Conference on Web and Wireless Geographical Information Systems (W2GIS'13), volume 7820 of Lecture Notes in Computer Science, pages 180-189. Springer, 2013. Google Scholar
  21. Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals. On the Complexity of Minimum-Link Path Problems. In Proceedings of the 32nd Annual Symposium on Computational Geometry (SoCG'16), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1-49:16. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016. Google Scholar
  22. Sarunas Marciuska and Johann Gamper. Determining Objects within Isochrones in Spatial Network Databases. In Proceedings of the 14th East European Conference on Advances in Databases and Information Systems (ADBIS'10), volume 6295 of Lecture Notes in Computer Science, pages 392-405. Springer, 2010. Google Scholar
  23. Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski. Minimum-Link Paths Revisited. Computational Geometry, 47(6):651-667, 2014. Google Scholar
  24. Joseph S. B. Mitchell, Günter Rote, and Gerhard Woeginger. Minimum-Link Paths Among Obstacles in the Plane. Algorithmica, 8(1):431-459, 1992. Google Scholar
  25. David O'Sullivan, Alastair Morrison, and John Shearer. Using Desktop GIS for the Investigation of Accessibility by Public Transport: An Isochrone Approach. International Journal of Geographical Information Science, 14(1):85-104, 2000. Google Scholar
  26. Subhash Suri. A Linear Time Algorithm for Minimum Link Paths Inside a Simple Polygon. Computer Vision, Graphics, and Image Processing, 35(1):99-110, 1986. Google Scholar
  27. Robert E. Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM, 22(2):215-225, 1975. Google Scholar
  28. Cao An Wang. Finding Minimal Nested Polygons. BIT Numerical Mathematics, 31(2):230-236, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact