28 citations · 33 across the 10 of their papers we have counts for
10 papers · 1 filter
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Bahareh Banyassady, Mark de Berg, Karl Bringmann +6
We consider the unlabeled motion-planning problem of unit-disc robots moving in a simple polygonal workspace of edges. The goal is to find a motion plan that moves the robo…
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves in , it provides a ro…
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertice…
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry
Karl Bringmann
Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectu…
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance
Karl Bringmann, Anne Driemel, André Nusser +1
We study the -approximate near neighbor problem under the continuous Fréchet distance: Given a set of polygonal curves with vertices, a radius , and a parameter $k…
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
Karl Bringmann, Marvin Künnemann, André Nusser
Consider the natural question of how to measure the similarity of curves in the plane by a quantity that is invariant under translations of the curves. Such a measure is justified…