BARC Talk by Sabine Storandt

Polylines rarely occur singly. When visualizing linear structures on maps or analyzing motion data, it is often necessary to consider large sets or bundles of polylines, whose interaction can be important for the application. In the talk, we first present a generalization of the classical polyline simplification to account for polyline bundles. The crucial aspect here is to ensure consistent simplification among shared parts. While a single polyline can be simplified to optimality in near-quadratic time, the generalized version leads to an APX-hard problem.

However, we show fixed-parameter tractability in the number of shared polyline points, and present a bi-criteria approximation algorithm that performs well on real data. In the second part of the talk, we consider range queries on (poly)line sets where the criterion to report an element depends on the interaction with the other lines in the range. For example, we want to report all line intersections in a given halfspace. We show that such queries can be answered output-sensitively after mild preprocessing effort.

Sabine Storandt will be visiting BARC from the 12th of June 2023, hosted by André Nusser.