Mark de Berg

activity

20242026

collaborators

Showing cs.CGShow all

4 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.CG2026

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 $P$ in Euclidean space is a classic geometric optimization problem. We consider the problem in a dynamic setting, where…

cs.CG2026

Optimal Motion Planning for Two Square Robots in a Rectilinear Environment

Pankaj K. Agarwal, Mark de Berg, Benjamin Holmgren +2

Let $W \subset R^{2}$ be a rectilinear polygonal environment (that is, a rectilinear polygon potentially with holes) with a total of $n$ vertices, and let $A, B$ be…

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

On the Stability of Minimum-Weight Perfect Matching on the Line

Optimal Motion Planning for Two Square Robots in a Rectilinear Environment

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