Search Results

Documents authored by Schäfer, Peter

Document
DOI: 10.4230/LIPIcs.SEA.2024.19
Algorithms for Gradual Polyline Simplification

Authors: Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Displaying line data is important in many visualization applications, and especially in the context of interactive geographical and cartographic visualization. When rendering linear features as roads, rivers or movement data on zoomable maps, the challenge is to display the data in an appropriate level of detail. A too detailed representation results in slow rendering and cluttered maps, while a too coarse representation might miss important data aspects. In this paper, we propose the gradual line simplification (GLS) problem, which aims to compute a fine-grained succession of consistent simplifications of a given input polyline with certain quality guarantees. The core concept of gradual simplification is to iteratively remove points from the polyline to obtain increasingly coarser representations. We devise two objective functions to guide this simplification process and present dynamic programs that compute the optimal solutions in 𝒪(n³) for an input line with n points. For practical application to large inputs, we also devise significantly faster greedy algorithms that provide constant factor guarantees for both problem variants at once. In an extensive experimental study on real-world data, we demonstrate that our algorithms are capable of producing simplification sequences of high quality within milliseconds on polylines consisting of over half a million points.
Cite as

Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt. Algorithms for Gradual Polyline Simplification. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{krumbholz_et_al:LIPIcs.SEA.2024.19,
  author =	{Krumbholz, Nick and Funke, Stefan and Sch\"{a}fer, Peter and Storandt, Sabine},
  title =	{{Algorithms for Gradual Polyline Simplification}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.19},
  URN =		{urn:nbn:de:0030-drops-203847},
  doi =		{10.4230/LIPIcs.SEA.2024.19},
  annote =	{Keywords: Polyline simplification, Progressive simplification, Fr\'{e}chet distance}
}
Document
Multimedia Exposition
DOI: 10.4230/LIPIcs.SoCG.2019.66
Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition)

Authors: Peter Schäfer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
The Fréchet-distance is a similarity measure for geometric shapes. Alt and Godau presented the first algorithm for computing the Fréchet-distance and introduced a key concept, the free-space diagram. Since then, numerous variants of the Fréchet-distance have been studied. We present here an interactive, graphical tool for exploring some Fréchet-distance algorithms. Given two curves, users can experiment with the free-space diagram and compute the Fréchet-distance. The Fréchet-distance can be computed for two important classes of shapes: for polygonal curves in the plane, and for simple polygonal surfaces. Finally, we demonstrate an implementation of a very recent concept, the k-Fréchet-distance.
Cite as

Peter Schäfer. Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 66:1-66:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schafer:LIPIcs.SoCG.2019.66,
  author =	{Sch\"{a}fer, Peter},
  title =	{{Fr\'{e}chet View - A Tool for Exploring Fr\'{e}chet Distance Algorithms}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{66:1--66:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.66},
  URN =		{urn:nbn:de:0030-drops-104703},
  doi =		{10.4230/LIPIcs.SoCG.2019.66},
  annote =	{Keywords: Fr\'{e}chet distance, free-space diagram, polygonal curves, simple polygons}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact