Polyline simplification has cubic complexity

Karl Bringmann, Bhaskar Ray Chaudhury

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(n3) time algorithm for simplification under Global-Fréchet distance, improving the previous best algorithm by a factor of Ω(kn2). 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(n3-ϵpoly(d)) for polyline simplification over (ℝd, Lp) for p = 1 would violate plausible conjectures. We obtain similar results for all p ∈ [1, ∞), p ≠ 2. In total, in high dimensions and over general Lp-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.

Original languageEnglish (US)
Title of host publication35th International Symposium on Computational Geometry, SoCG 2019
EditorsGill Barequet, Yusu Wang
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771047
DOIs
StatePublished - Jun 1 2019
Externally publishedYes
Event35th International Symposium on Computational Geometry, SoCG 2019 - Portland, United States
Duration: Jun 18 2019Jun 21 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume129
ISSN (Print)1868-8969

Conference

Conference35th International Symposium on Computational Geometry, SoCG 2019
Country/TerritoryUnited States
CityPortland
Period6/18/196/21/19

Keywords

  • Conditional lower bounds
  • Fréchet distance
  • Hausdorff distance
  • Polyline simplification

ASJC Scopus subject areas

  • Software

Cite this