M. de Berg

activity

20072026

most citedIndependent Set Reconfiguration Thresholds of Hereditary Graph Classes

10 citations · 18 across the 13 of their papers we have counts for

collaborators

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

cs.DS2023

Finding Diverse Minimum s-t Cuts

Mark de Berg, Andrés López Martínez, Frits Spieksma

Recently, many studies have been devoted to finding diverse solutions in classical combinatorial problems, such as Vertex Cover (Baste et al., IJCAI'20), Matching (Fomin et al., IS…

cs.DS2023★ 2 cited

$k$ -Center Clustering with Outliers in the MPC and Streaming Model

Mark de Berg, Leyla Biabani, Morteza Monemizadeh

Given a point set $P \subseteq X$ of size $n$ in a metric space $(X, d i s t)$ of doubling dimension $d$ and two parameters $k \in N$ and $z \in N$ , the $k$ -center problem with $z$ out…

cs.CG2022

Computing Smallest Convex Intersecting Polygons

Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak +1

A polygon C is an intersecting polygon for a set O of objects in the plane if C intersects each object in O, where the polygon includes its interior. We study the problem of comput…

cs.CG2022

Partitioning axis-parallel lines in 3D

Boris Aronov, Abdul Basit, Mark de Berg +1

Let $L$ be a set of $n$ axis-parallel lines in $R^{3}$ . We are are interested in partitions of $R^{3}$ by a set $H$ of three planes such that each open cell in the ar…

cs.CG2021

Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

Mark de Berg, Arpan Sadhukhan, Frits Spieksma

Let $P$ be a set of points in $R^{d}$ , where each point $p \in P$ has an associated transmission range $ρ (p)$ . The range assignment $ρ$ induces a directed communication graph…

cs.CG2020★ 1 cited

Euclidean TSP in Narrow Strips

Henk Alkema, Mark de Berg, Remco van der Hofstad +1

We investigate how the complexity of Euclidean TSP for point sets $P$ inside the strip $(- \infty, + \infty) \times [0, δ]$ depends on the strip width $δ$ . We obtain two main results. F…

cs.CG2018★ 1 cited

An ETH-Tight Exact Algorithm for Euclidean TSP

Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak +1

We study exact algorithms for Euclidean TSP in $R^{d}$ . In the early 1990s algorithms with $n^{O (n)}$ running time were presented for the planar case, and some years…

cs.CG2017

Minimum Perimeter-Sum Partitions in the Plane

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin +2

Let $P$ be a set of $n$ points in the plane. We consider the problem of partitioning $P$ into two subsets $P_{1}$ and $P_{2}$ such that the sum of the perimeters of $CH (P_{1})$ an…

cs.CG2017

Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points

Mark de Berg, Tim Leijsen, André van Renssen +3

We introduce the fully-dynamic conflict-free coloring problem for a set $S$ of intervals in $R^{1}$ with respect to points, where the goal is to maintain a conflict-free col…

cs.CG2017

Removing Depth-Order Cycles Among Triangles: An Efficient Algorithm Generating Triangular Fragments

Mark de Berg

More than 25 years ago Chazelle~\emph{et al.} (FOCS 1991) studied the following question: Is it possible to cut any set of $n$ lines in $R^{3}$ into a subquadratic number of f…

math.MG2016

Shortcuts for the Circle

Sang Won Bae, Mark de Berg, Otfried Cheong +2

Let $C$ be the unit circle in $R^{2}$ . We can view $C$ as a plane graph whose vertices are all the points on $C$ , and the distance between any two points on $C$ is the lengt…

cs.DM2016★ 10 cited

Independent Set Reconfiguration Thresholds of Hereditary Graph Classes

Mark de Berg, Bart M. P. Jansen, Debankur Mukherjee

Traditionally, reconfiguration problems ask the question whether a given solution of an optimization problem can be transformed to a target solution in a sequence of small steps th…

cs.CG2016★ 1 cited

Distance-Sensitive Planar Point Location

Boris Aronov, Mark de Berg, David Eppstein +2

Let $S$ be a connected planar polygonal subdivision with $n$ edges that we want to preprocess for point-location queries, and where we are given the probability $γ_{i}$ tha…

cs.CG2015

Geodesic Spanners for Points on a Polyhedral Terrain

Mohammad Ali Abam, Mark de Berg, Mohammad Javad Rezaei Seraji

We show that there exists a geodesic spanner with almost linear number of edges.

cs.CG2010

Treemaps with Bounded Aspect Ratio

Mark de Berg, Bettina Speckmann, Vincent van der Weele

Treemaps are a popular technique to visualize hierarchical data. The input is a weighted tree $\tree$ where the weight of each node is the sum of the weights of its children. A tre…

cs.CG2010★ 1 cited

The Traveling Salesman Problem Under Squared Euclidean Distances

Mark de Berg, Fred van Nijnatten, René Sitters +2

Let $P$ be a set of points in $R^{d}$ , and let $α \geq 1$ be a real number. We define the distance between two points $p, q \in P$ as $∣ pq ∣^{α}$ , where $∣ pq ∣$ denotes the standard…

cs.CG2007★ 2 cited

Sparse geometric graphs with small dilation

Boris Aronov, Mark de Berg, Otfried Cheong +4

Given a set S of n points in R^D, and an integer k such that 0 <= k < n, we show that a geometric graph with vertex set S, at most n - 1 + k edges, maximum degree five, and dilatio…

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

Finding Diverse Minimum s-t Cuts

k-Center Clustering with Outliers in the MPC and Streaming Model

Computing Smallest Convex Intersecting Polygons

Partitioning axis-parallel lines in 3D

Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

Euclidean TSP in Narrow Strips

An ETH-Tight Exact Algorithm for Euclidean TSP

Minimum Perimeter-Sum Partitions in the Plane

Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points

Removing Depth-Order Cycles Among Triangles: An Efficient Algorithm Generating Triangular Fragments

Shortcuts for the Circle

Independent Set Reconfiguration Thresholds of Hereditary Graph Classes

Distance-Sensitive Planar Point Location

Geodesic Spanners for Points on a Polyhedral Terrain

Treemaps with Bounded Aspect Ratio

The Traveling Salesman Problem Under Squared Euclidean Distances

Sparse geometric graphs with small dilation

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

$k$ -Center Clustering with Outliers in the MPC and Streaming Model