  The Polyline Bundle Simplification (PBS) problem is a generalization of the
classical polyline simplification problem. Given a set of polylines, which may
share line segments and points, PBS asks for the smallest consistent
simplification of these polylines with respect to a given distance threshold.
Here, consistent means that each point is either kept in or discarded from all
polylines containing it. In previous work, it was proven that PBS is NP-hard to
approximate within a factor of $n^{\frac{1}{3}-\varepsilon}$ for any
$\varepsilon > 0$ where $n$ denotes the number of points in the input. This
hardness result holds even for two polylines. In this paper we first study the
practically relevant setting of planar inputs. While for many combinatorial
optimization problems the restriction to planar settings makes the problem
substantially easier, we show that the inapproximability bound known for
general inputs continues to hold even for planar inputs. We proceed with the
interesting special case of PBS where the polylines form a rooted tree. Such
tree bundles naturally arise in the context of movement data visualization. We
prove that optimal simplifications of these tree bundles can be computed in
$O(n^3)$ for the Fr\'echet distance and in $O(n^2)$ for the Hausdorff distance
(which both match the computation time for single polylines). Furthermore, we
present a greedy heuristic that allows to decompose polyline bundles into tree
bundles in order to make our exact algorithm for trees useful on general
inputs. The applicability of our approaches is demonstrated in an experimental
evaluation on real-world data.
