2026-08-11T08:08:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12282 2024-03-06T10:49:31Z ddc:004 open_access

Simplification of Polyline Bundles Spoerhase, Joachim Storandt, Sabine Zink, Johannes Polyline Simplification Bi-criteria Approximation Hardness of Approximation Geometric Set Cover We propose and study a generalization to the well-known problem of polyline simplification. Instead of a single polyline, we are given a set of l polylines possibly sharing some line segments and bend points. Our goal is to minimize the number of bend points in the simplified bundle with respect to some error tolerance δ (measuring Fréchet distance) but under the additional constraint that shared parts have to be simplified consistently. We show that polyline bundle simplification is NP-hard to approximate within a factor n^(1/3 - ε) for any ε > 0 where n is the number of bend points in the polyline bundle. This inapproximability even applies to instances with only l=2 polylines. However, we identify the sensitivity of the solution to the choice of δ as a reason for this strong inapproximability. In particular, we prove that if we allow δ to be exceeded by a factor of 2 in our solution, we can find a simplified polyline bundle with no more than 𝒪(log (l + n)) ⋅ OPT bend points in polytime, providing us with an efficient bi-criteria approximation. As a further result, we show fixed-parameter tractability in the number of shared bend points. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joachim Spoerhase and Sabine Storandt and Johannes Zink 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.35 urn:nbn:de:0030-drops-122821 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.35 eng https://creativecommons.org/licenses/by/3.0/legalcode