4 papers
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…
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.…
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…