31 citations · 116 across the 24 of their papers we have counts for
3 papers · 2 filters
Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
Mikkel Abrahamsen, Kevin Buchin, Maike Buchin +5
We study two well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the sta…
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…