Mark de Berg

activity

20202026

most citedApproximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency

3 citations · 3 across the 4 of their papers we have counts for

collaborators

Showing cs.CGShow all

2 papers · 1 filter

cs.CG2026

On Linear-Size Guillotine-Separable Subsets of Fat Convex Objects, Disks, and Squares

Mark de Berg, Debajyoti Kar, Arindam Khan +1

Let $K$ be a family of pairwise disjoint objects in the plane. We say that a subset $K^{*} \subseteq K$ is \emph{separable} if it admits a sequence of gu…

cs.CG2025

An $O (n lo g n)$ 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 $O (n lo g n)$ time, and that it can be solved on intersection graphs of fat triangles in $O(n\l…

On Linear-Size Guillotine-Separable Subsets of Fat Convex Objects, Disks, and Squares

An O(nlogn) Algorithm for Single-Source Shortest Paths in Disk Graphs

An $O (n lo g n)$ Algorithm for Single-Source Shortest Paths in Disk Graphs