8 papers
On Linear-Size Guillotine-Separable Subsets of Fat Convex Objects, Disks, and Squares
Mark de Berg, Debajyoti Kar, Arindam Khan +1
Let be a family of pairwise disjoint objects in the plane. We say that a subset is \emph{separable} if it admits a sequence of gu…
On the Stability of Minimum-Weight Perfect Matching on the Line
Mark de Berg, Ulrike Schmidt-Kraepelin, Andree-Ovidiu Stef
Computing a minimum-weight perfect matching for a point set in Euclidean space is a classic geometric optimization problem. We consider the problem in a dynamic setting, where…
Optimal Motion Planning for Two Square Robots in a Rectilinear Environment
Pankaj K. Agarwal, Mark de Berg, Benjamin Holmgren +2
Let be a rectilinear polygonal environment (that is, a rectilinear polygon potentially with holes) with a total of vertices, and let be…
Disjoint Tours and the Price of Diversity
Mark de Berg, Andrés López MartÃnez, Frits Spieksma
We study a variant of the Traveling Salesman Problem, where instead of finding a single tour, we want to find a pair of two edge-disjoint tours whose longer tour is as short as pos…
Parameterized Complexity of Directed Traveling Salesman Problem
Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes +2
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be vi…
An Algorithm for Single-Source Shortest Paths in Disk Graphs
Mark de Berg, Sergio Cabello
We prove that the single-source shortest-path problem on disk graphs can be solved in time, and that it can be solved on intersection graphs of fat triangles in $O(n\l…