22 citations · 28 across the 13 of their papers we have counts for
24 papers
Linear time single-source shortest path algorithms in Euclidean graph classes
Joachim Gudmundsson, Yuan Sha, Sampson Wong
In the celebrated paper of Henzinger, Klein, Rao and Subramanian (1997), it was shown that planar graphs admit a linear time single-source shortest path algorithm. Their algorithm…
Minimum Exposure Motion Planning
Sarita de Berg, Joachim Gudmundsson, Peter Kramer +2
We investigate multiple fundamental variants of the classic coordinated motion planning (CMP) problem for unit square robots in the plane under the metric. In coordinated mot…
A WSPD, Separator and Small Tree Cover for c-packed Graphs
Lindsey Deryckere, Joachim Gudmundsson, André van Renssen +2
The -packedness property, proposed in 2010, is a geometric property that captures the spatial distribution of a set of edges. Despite the recent interest in -packedness, its…
A well-separated pair decomposition for low density graphs
Joachim Gudmundsson, Sampson Wong
Low density graphs are considered to be a realistic graph class for modelling road networks. It has advantages over other popular graph classes for road networks, such as planar gr…
Map-Matching Queries under Fréchet Distance on Low-Density Spanners
Kevin Buchin, Maike Buchin, Joachim Gudmundsson +2
Map matching is a common task when analysing GPS tracks, such as vehicle trajectories. The goal is to match a recorded noisy polygonal curve to a path on the map, usually represent…
Bicriteria approximation for minimum dilation graph augmentation
Kevin Buchin, Maike Buchin, Joachim Gudmundsson +1
Spanner constructions focus on the initial design of the network. However, networks tend to improve over time. In this paper, we focus on the improvement step. Given a graph and a…
Spanner for the weighted region problem
Joachim Gudmundsson, Zijin Huang, André van Renssen +1
We consider the problem of computing an approximate weighted shortest path in a weighted subdivision, with weights assigned from the set . We present a data struc…
Approximating the Fréchet distance when only one curve is -packed
Joachim Gudmundsson, Tiancheng Mai, Sampson Wong
One approach to studying the Fréchet distance is to consider curves that satisfy realistic assumptions. By now, the most popular realistic assumption for curves is -packedness.…
Computing a Subtrajectory Cluster from c-packed Trajectories
Joachim Gudmundsson, Zijin Huang, André van Renssen +1
We present a near-linear time approximation algorithm for the subtrajectory cluster problem of -packed trajectories. The problem involves finding subtrajectories within a gi…
Oriented Spanners
Kevin Buchin, Joachim Gudmundsson, Antonia Kalb +4
Given a point set in the Euclidean plane and a parameter , we define an \emph{oriented -spanner} as an oriented subgraph of the complete bi-directed graph such that f…
Data Structures for Approximate Discrete Fréchet Distance
Ivor van der Hoog, Eva Rotenberg, Sampson Wong
The Fréchet distance is a popular distance measure between curves and . Conditional lower bounds prohibit -approximate Fréchet distance computations in st…
Approximating the lambda-low-density value
Joachim Gudmundsson, Zijin Huang, Sampson Wong
The use of realistic input models has gained popularity in the theory community. Assuming a realistic input model often precludes complicated hypothetical inputs, and the analysis…
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
Andrè van Renssen, Yuan Sha, Yucheng Sun +1
Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed…
Map matching queries on realistic input graphs under the Fréchet distance
Joachim Gudmundsson, Martin P. Seybold, Sampson Wong
Map matching is a common preprocessing step for analysing vehicle trajectories. In the theory community, the most popular approach for map matching is to compute a path on the road…
Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time
Kevin Buchin, André Nusser, Sampson Wong
Dynamic Time Warping is arguably the most popular similarity measure for time series, where we define a time series to be a one-dimensional polygonal curve. The drawback of Dynamic…
Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size
Joachim Gudmundsson, Martin P. Seybold, Sampson Wong
Given a set of sites from , each having some positive weight factor, the Multiplicatively Weighted Voronoi Diagram is a subdivision of space that associates each…
Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance
Joachim Gudmundsson, Sampson Wong
Detecting commuting patterns or migration patterns in movement data is an important problem in computational movement analysis. Given a trajectory, or set of trajectories, this cor…
Translation Invariant Fréchet Distance Queries
Joachim Gudmundsson, André van Renssen, Zeinab Saeidi +1
The Fréchet distance is a popular similarity measure between curves. For some applications, it is desirable to match the curves under translation before computing the Fréchet dista…
Covering a set of line segments with a few squares
Joachim Gudmundsson, Mees van de Kerkhof, André van Renssen +3
We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments…
(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping
Milutin Brankovic, Kevin Buchin, Koen Klaren +3
Due to the massively increasing amount of available geospatial data and the need to present it in an understandable way, clustering this data is more important than ever. As cluste…
Approximating the packedness of polygonal curves
Joachim Gudmundsson, Yuan Sha, Sampson Wong
In 2012 Driemel et al. \cite{DBLP:journals/dcg/DriemelHW12} introduced the concept of -packed curves as a realistic input model. In the case when is a constant they gave a n…
Improving the dilation of a metric graph by adding edges
Joachim Gudmundsson, Sampson Wong
Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this…
Computing the Yolk in Spatial Voting Games without Computing Median Lines
Joachim Gudmundsson, Sampson Wong
The yolk is an important concept in spatial voting games as it generalises the equilibrium and provides bounds on the uncovered set. We present near-linear time algorithms for comp…
An algorithm for the Euclidean cell decomposition of a cusped strictly convex projective surface
Stephan Tillmann, Sampson Wong
Cooper and Long generalised Epstein and Penner's Euclidean cell decomposition of cusped hyperbolic manifolds of finite volume to non-compact strictly convex projective manifolds of…