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.2019.18
URN: urn:nbn:de:0030-drops-104224
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10422/
Go to the corresponding LIPIcs Volume Portal

Bringmann, Karl ; Chaudhury, Bhaskar Ray

Polyline Simplification has Cubic Complexity

pdf-format:
LIPIcs-SoCG-2019-18.pdf (0.8 MB)

Abstract

In the classic polyline simplification problem we want to replace a given polygonal curve P, consisting of n vertices, by a subsequence P' of k vertices from P such that the polygonal curves P and P' are "close". Closeness is usually measured using the Hausdorff or Fréchet distance. These distance measures can be applied globally, i.e., to the whole curves P and P', or locally, i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). We provide an O(n^3) time algorithm for simplification under Global-Fréchet distance, improving the previous best algorithm by a factor of Omega(kn^2). We also provide evidence that in high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Fréchet, and Global-Fréchet). Specifically, improving the cubic time to O(n^{3-epsilon} poly(d)) for polyline simplification over (R^d,L_p) for p = 1 would violate plausible conjectures. We obtain similar results for all p in [1,infty), p != 2. In total, in high dimensions and over general L_p-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fréchet, and Global-Fréchet, by providing new algorithms and conditional lower bounds.

BibTeX - Entry

@InProceedings{bringmann_et_al:LIPIcs:2019:10422,
  author =	{Karl Bringmann and Bhaskar Ray Chaudhury},
  title =	{{Polyline Simplification has Cubic Complexity}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10422},
  URN =		{urn:nbn:de:0030-drops-104224},
  doi =		{10.4230/LIPIcs.SoCG.2019.18},
  annote =	{Keywords: Polyline simplification, Fr{\'e}chet distance, Hausdorff distance, Conditional lower bounds}
}

Keywords: Polyline simplification, Fréchet distance, Hausdorff distance, Conditional lower bounds
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

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