License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.56
URN: urn:nbn:de:0030-drops-87694
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8769/
Go to the corresponding LIPIcs Volume Portal

van Kreveld, Marc ; Löffler, Maarten ; Wiratma, Lionov

On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance

pdf-format:
LIPIcs-SoCG-2018-56.pdf (0.8 MB)

Abstract

We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given epsilon>0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most epsilon.
We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than epsilon. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of n vertices under the Fréchet distance, we give an O(kn^5) time algorithm that requires O(kn^2) space, where k is the output complexity of the simplification.

BibTeX - Entry

@InProceedings{vankreveld_et_al:LIPIcs:2018:8769,
  author =	{Marc van Kreveld and Maarten L{\"o}ffler and Lionov Wiratma},
  title =	{{On Optimal Polyline Simplification Using the Hausdorff and Fr{\'e}chet Distance}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8769},
  URN =		{urn:nbn:de:0030-drops-87694},
  doi =		{10.4230/LIPIcs.SoCG.2018.56},
  annote =	{Keywords: polygonal line simplification, Hausdorff distance, Fr{\'e}chet distance, Imai-Iri, Douglas-Peucker}
}

Keywords: polygonal line simplification, Hausdorff distance, Fréchet distance, Imai-Iri, Douglas-Peucker
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI