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

Showing cs.CGShow all

16 papers · 1 filter

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

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

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

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

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

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}$