文章基本信息
- 标题：Simplification of Polyline Bundles
- 本地全文：下载
- 作者：Joachim Spoerhase ; Sabine Storandt ; Johannes Zink 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：162
- 页码：35:1-35:20
- DOI：10.4230/LIPIcs.SWAT.2020.35
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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.
- 关键词：Polyline Simplification; Bi-criteria Approximation; Hardness of Approximation; Geometric Set Cover
