1 Search Results for "Gemsa, Andreas"

Document
DOI: 10.4230/LIPIcs.ESA.2016.7
Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths

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

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{baum_et_al:LIPIcs.ESA.2016.7,
  author =	{Baum, Moritz and Bl\"{a}sius, Thomas and Gemsa, Andreas and Rutter, Ignaz and Wegner, Franziska},
  title =	{{Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.7},
  URN =		{urn:nbn:de:0030-drops-63498},
  doi =		{10.4230/LIPIcs.ESA.2016.7},
  annote =	{Keywords: isocontours, separating polygons, minimum-link paths}
}
  • Refine by Author
  • 1 Baum, Moritz
  • 1 Bläsius, Thomas
  • 1 Gemsa, Andreas
  • 1 Rutter, Ignaz
  • 1 Wegner, Franziska

  • Refine by Classification

  • Refine by Keyword
  • 1 isocontours
  • 1 minimum-link paths
  • 1 separating polygons

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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 Imprint Privacy Contact