BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Mark de Berg

Mark de Berg contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryArtificial IntelligenceData Structures and AlgorithmsRoboticsMultiagent Systems

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2026arXiv

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs

Recently it was shown that many classic graph problems -- Independent Set, Dominating Set, Hamiltonian Cycle, and more -- can be solved in subexponential time on unit-ball graphs. More precisely, these problems can be solved in $2^{O(n^{1-1/d})}$ time on unit-ball graphs in $\mathbb R^d$, which is tight under ETH. The result can be generalized to intersection graphs of similarly-sized fat objects. For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove that - there is no algorithm with running time $2^{o(n)}$ for Dominating Set on (non-unit) ball graphs in $\mathbb R^3$; - there is no algorithm with running time $2^{o(n)}$ for Weighted Dominating Set on unit-ball graphs in $\mathbb R^3$; - there is no algorithm with running time $2^{o(n)}$ for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Computing Smallest Convex Intersecting Polygons

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 computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n. Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency $L$ of a schedule is the maximum latency of any site, where the latency of a site $s$ is the supremum of the lengths of the time intervals between consecutive visits to $s$. When $k=1$ the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into $\ell$ groups, for some~$\ell \leq k$, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a $1+\varepsilon$ factor loss in the approximation factor and an $O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for any $\varepsilon >0$. Our second main result shows that an optimal cyclic solution is a $2(1-1/k)$-approximation of the overall optimal solution. Note that for $k=2$ this implies that an optimal cyclic solution is optimal overall. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a $(2(1-1/k)+\varepsilon)$-approximation of the optimal unrestricted solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time $O(n \log n + mn + m^2)$ if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance $4$ apart, any two target positions are at least distance $4$ apart, and any pair of a start and a target positions is at least distance $3$ apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Minimum Perimeter-Sum Partitions in the Plane

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 $\text{CH}(P_1)$ and $\text{CH}(P_2)$ is minimized, where $\text{CH}(P_i)$ denotes the convex hull of $P_i$. The problem was first studied by Mitchell and Wynters in 1991 who gave an $O(n^2)$ time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in $O(n \log^2 n)$ time and a $(1+\varepsilon)$-approximation algorithm running in $O(n + 1/\varepsilon^2\cdot\log^2(1/\varepsilon))$ time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency

We consider the problem of finding patrol schedules for $k$ robots to visit a given set of $n$ sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when $k=1$ and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of $O(k^2 \log \frac{w_{\max}}{w_{\min}})$ to the optimal solution, where $w_{\max}$ and $w_{\min}$ are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a $12$-approximate solution, which runs in polynomial time when the number of robots, $k$, is a constant.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On beta-Plurality Points in Spatial Voting Games

Let $V$ be a set of $n$ points in $\mathbb{R}^d$, called voters. A point $p\in \mathbb{R}^d$ is a plurality point for $V$ when the following holds: for every $q\in\mathbb{R}^d$ the number of voters closer to $p$ than to $q$ is at least the number of voters closer to $q$ than to $p$. Thus, in a vote where each $v\in V$ votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal $p$ will not lose against any alternative proposal $q$. For most voter sets a plurality point does not exist. We therefore introduce the concept of $β$-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to $p$ (but not to $q$) is scaled by a factor $β$, for some constant $0<β\leq 1$. We investigate the existence and computation of $β$-plurality points, and obtain the following. * Define $β^*_d := \sup \{ β: \text{any finite multiset $V$ in $\mathbb{R}^d$ admits a $β$-plurality point} \}$. We prove that $β^*_2 = \sqrt{3}/2$, and that $1/\sqrt{d} \leq β^*_d \leq \sqrt{3}/2$ for all $d\geq 3$. * Define $β(p, V) := \sup \{ β: \text{$p$ is a $β$-plurality point for $V$}\}$. Given a voter set $V \in \mathbb{R}^2$, we provide an algorithm that runs in $O(n \log n)$ time and computes a point $p$ such that $β(p, V) \geq β^*_2$. Moreover, for $d\geq 2$ we can compute a point $p$ with $β(p,V) \geq 1/\sqrt{d}$ in $O(n)$ time. * Define $β(V) := \sup \{ β: \text{$V$ admits a $β$-plurality point}\}$. We present an algorithm that, given a voter set $V$ in $\mathbb{R}^d$, computes an $(1-\varepsilon)\cdot β(V)$ plurality point in time $O(\frac{n^2}{\varepsilon^{3d-2}} \cdot \log \frac{n}{\varepsilon^{d-1}} \cdot \log^2 \frac {1}{\varepsilon})$.

0 citations0 reviewsNo code linkedOpen access