Bringmann, Karl ;
Chaudhury, Bhaskar Ray
Polyline Simplification has Cubic Complexity
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 GlobalFré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 (LocalHausdorff, LocalFréchet, and GlobalFréchet). Specifically, improving the cubic time to O(n^{3epsilon} 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_pnorms we resolve the complexity of polyline simplification with respect to LocalHausdorff, LocalFréchet, and GlobalFré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:118:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10422},
URN = {urn:nbn:de:0030drops104224},
doi = {10.4230/LIPIcs.SoCG.2019.18},
annote = {Keywords: Polyline simplification, Fr{\'e}chet distance, Hausdorff distance, Conditional lower bounds}
}
2019
Keywords: 

Polyline simplification, Fréchet distance, Hausdorff distance, Conditional lower bounds 
Seminar: 

35th International Symposium on Computational Geometry (SoCG 2019)

Issue date: 

2019 
Date of publication: 

2019 