1 citations · 2 across the 6 of their papers we have counts for
6 papers
Dynamic Dynamic Time Warping
Karl Bringmann, Nick Fischer, Ivor van der Hoog +3
The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, espe…
Adaptive Out-Orientations with Applications
Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm +4
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…
Simple and Robust Dynamic Two-Dimensional Convex Hull
Emil Toftegaard Gæde, Inge Li Gørtz, Ivor van der Hoog +2
The convex hull of a data set is the smallest convex set that contains . In this work, we present a new data structure for convex hull, that allows for efficient dynamic upd…
Triangulations Admit Dominating Sets of Size
Aleksander B. G. Christiansen, Eva Rotenberg, Daniel Rutschmann
We show that every planar triangulation on vertices has a dominating set of size . This approaches the bound conjectured by Matheson and Tarjan [MT'96], and…
Planar Reachability in Linear Space and Constant Time
Jacob Holm, Eva Rotenberg, Mikkel Thorup
We show how to represent a planar digraph in linear space so that distance queries can be answered in constant time. The data structure can be constructed in linear time. This repr…
Faster Fully-Dynamic Minimum Spanning Forest
Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen
We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in amortized time per operat…