7 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…
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…
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…
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…
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…