M. de Berg

collaborators

4 papers

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.GT2024

Truthful Budget Aggregation: Beyond Moving-Phantom Mechanisms

Mark de Berg, Rupert Freeman, Ulrike Schmidt-Kraepelin +1

We study a budget-aggregation setting in which a number of voters report their ideal distribution of a budget over a set of alternatives, and a mechanism aggregates these reports i…

cs.CG2024

A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $R^{2}$

Boris Aronov, Mark de Berg, Leonidas Theocharous

Let $d$ be a (well-behaved) shortest-path metric defined on a path-connected subset of $R^{2}$ and let $D = {D_{1}, \dots, D_{n}}$ be a set of geodesic disks with respe…

cs.CG2024

A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon

Mark de Berg, Leonidas Theocharous

Let $P$ be a simple polygon with $m$ vertices and let $P$ be a set of $n$ points inside $P$ . We prove that there exists, for any $ε > 0$ , a set $\mathca…

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

Truthful Budget Aggregation: Beyond Moving-Phantom Mechanisms

A Clique-Based Separator for Intersection Graphs of Geodesic Disks in R2

A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon

A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $R^{2}$