Source author record

Mark de Berg

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Robotics Artificial Intelligence Computational Complexity Multiagent Systems

Catalog footprint

Research overview

15works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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.

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.

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.

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.

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.

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

preprint2016arXiv

Distance-Sensitive Planar Point Location

Let $\mathcal{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$ that the query point lies in a polygon $P_i$ of $\mathcal{S}$ . We show how to preprocess $\mathcal{S}$ such that the query time for a point~ $p\in P_i$ depends on~ $γ_i$ and, in addition, on the distance from $p$ to the boundary of~ $P_i$ ---the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time $O\left(\min \left(\log n, 1 + \log \frac{\mathrm{area}(P_i)}{γ_i Δ_{p}^2}\right)\right)$ , where $Δ_{p}$ is the shortest Euclidean distance of the query point~ $p$ to the boundary of $P_i$ . Our structure uses $O(n)$ space and $O(n \log n)$ preprocessing time. It is based on a decomposition of the regions of $\mathcal{S}$ into convex quadrilaterals and triangles with the following property: for any point $p\in P_i$ , the quadrilateral or triangle containing~ $p$ has area $Ω(Δ_{p}^2)$ . For the special case where $\mathcal{S}$ is a subdivision of the unit square and $γ_i=\mathrm{area}(P_i)$ , we present a simpler solution that achieves a query time of $O\left(\min \left(\log n, \log \frac{1}{Δ_{p}^2}\right)\right)$ . The latter solution can be extended to convex subdivisions in three dimensions.

preprint2016arXiv

Fine-Grained Complexity Analysis of Two Classic TSP Variants

We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity. Our first set of results is motivated by the Bitonic TSP problem: given a set of $n$ points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamic-programming exercise to solve this problem in $O(n^2)$ time. While the near-quadratic dependency of similar dynamic programs for Longest Common Subsequence and Discrete Frechet Distance has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic TSP in $O(n \log^2 n)$ time and its bottleneck version in $O(n \log^3 n)$ time. Our second set of results concerns the popular $k$ -OPT heuristic for TSP in the graph setting. More precisely, we study the $k$ -OPT decision problem, which asks whether a given tour can be improved by a $k$ -OPT move that replaces $k$ edges in the tour by $k$ new edges. A simple algorithm solves $k$ -OPT in $O(n^k)$ time for fixed $k$ . For 2-OPT, this is easily seen to be optimal. For $k=3$ we prove that an algorithm with a runtime of the form $\tilde{O}(n^{3-ε})$ exists if and only if All-Pairs Shortest Paths in weighted digraphs has such an algorithm. The results for $k=2,3$ may suggest that the actual time complexity of $k$ -OPT is $Θ(n^k)$ . We show that this is not the case, by presenting an algorithm that finds the best $k$ -move in $O(n^{\lfloor 2k/3 \rfloor + 1})$ time for fixed $k \geq 3$ . This implies that 4-OPT can be solved in $O(n^3)$ time, matching the best-known algorithm for 3-OPT. Finally, we show how to beat the quadratic barrier for $k=2$ in two important settings, namely for points in the plane and when we want to solve 2-OPT repeatedly.

preprint2015arXiv

Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons

We consider the following motion-planning problem: we are given $m$ unit discs in a simple polygon with $n$ vertices, each at their own start position, and we want to move the discs to a given set of $m$ target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in $O(n\log n+mn+m^2)$ time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion-planning problem for discs moving in a simple polygon, which is known to be strongly NP-hard.

preprint2015arXiv

Finding Pairwise Intersections Inside a Query Range

We study the following problem: preprocess a set O of objects into a data structure that allows us to efficiently report all pairs of objects from O that intersect inside an axis-aligned query range Q. We present data structures of size $O(n({\rm polylog} n))$ and with query time $O((k+1)({\rm polylog} n))$ time, where k is the number of reported pairs, for two classes of objects in the plane: axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in R^3, we present a data structures of size $O(n\sqrt{n}({\rm polylog} n))$ and query time $O((\sqrt{n}+k)({\rm polylog} n))$ . When the objects and query are fat, we obtain $O((k+1)({\rm polylog} n))$ query time using $O(n({\rm polylog} n))$ storage.

preprint2015arXiv

Geodesic Spanners for Points on a Polyhedral Terrain

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

preprint2013arXiv

Fat Polygonal Partitions with Applications to Visualization and Embeddings

Let $\mathcal{T}$ be a rooted and weighted tree, where the weight of any node is equal to the sum of the weights of its children. The popular Treemap algorithm visualizes such a tree as a hierarchical partition of a square into rectangles, where the area of the rectangle corresponding to any node in $\mathcal{T}$ is equal to the weight of that node. The aspect ratio of the rectangles in such a rectangular partition necessarily depends on the weights and can become arbitrarily high. We introduce a new hierarchical partition scheme, called a polygonal partition, which uses convex polygons rather than just rectangles. We present two methods for constructing polygonal partitions, both having guarantees on the worst-case aspect ratio of the constructed polygons; in particular, both methods guarantee a bound on the aspect ratio that is independent of the weights of the nodes. We also consider rectangular partitions with slack, where the areas of the rectangles may differ slightly from the weights of the corresponding nodes. We show that this makes it possible to obtain partitions with constant aspect ratio. This result generalizes to hyper-rectangular partitions in $\mathbb{R}^d$ . We use these partitions with slack for embedding ultrametrics into $d$ -dimensional Euclidean space: we give a $\mathop{\rm polylog}(Δ)$ -approximation algorithm for embedding $n$ -point ultrametrics into $\mathbb{R}^d$ with minimum distortion, where $Δ$ denotes the spread of the metric, i.e., the ratio between the largest and the smallest distance between two points. The previously best-known approximation ratio for this problem was polynomial in $n$ . This is the first algorithm for embedding a non-trivial family of weighted-graph metrics into a space of constant dimension that achieves polylogarithmic approximation ratio.

preprint2011arXiv

Treemaps with Bounded Aspect Ratio

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 treemap for $\tree$ is a hierarchical partition of a rectangle into simply connected regions, usually rectangles. Each region represents a node of $\tree$ and its area is proportional to the weight of the corresponding node. An important quality criterion for treemaps is the aspect ratio of its regions. One cannot bound the aspect ratio if the regions are restricted to be rectangles. In contrast, \emph{polygonal partitions}, that use convex polygons, have bounded aspect ratio. We are the first to obtain convex partitions with optimal aspect ratio $O(\depth(\tree))$. However, $\depth(\tree)$ still depends on the input tree. Hence we introduce a new type of treemaps, namely \emph{orthoconvex treemaps}, where regions representing leaves are rectangles, L-, and S-shapes, and regions representing internal nodes are orthoconvex polygons. We prove that any input tree, irrespective of the weights of the nodes and the depth of the tree, admits an orthoconvex treemap of constant aspect ratio. We also obtain several specialized results for single-level treemaps, that is, treemaps where the input tree has depth~1.

preprint2010arXiv

The Traveling Salesman Problem Under Squared Euclidean Distances

Let $P$ be a set of points in $\mathbb{R}^d$ , and let $α\ge 1$ be a real number. We define the distance between two points $p,q\in P$ as $|pq|^α$ , where $|pq|$ denotes the standard Euclidean distance between $p$ and $q$ . We denote the traveling salesman problem under this distance function by TSP( $d,α$ ). We design a 5-approximation algorithm for TSP(2,2) and generalize this result to obtain an approximation factor of $3^{α-1}+\sqrt{6}^α/3$ for $d=2$ and all $α\ge2$ . We also study the variant Rev-TSP of the problem where the traveling salesman is allowed to revisit points. We present a polynomial-time approximation scheme for Rev-TSP $(2,α)$ with $α\ge2$ , and we show that Rev-TSP $(d, α)$ is APX-hard if $d\ge3$ and $α>1$ . The APX-hardness proof carries over to TSP $(d, α)$ for the same parameter ranges.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Mark de Berg

Research overview

Is this your work?

15 publications

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

Computing Smallest Convex Intersecting Polygons

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

Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

Minimum Perimeter-Sum Partitions in the Plane

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

On beta-Plurality Points in Spatial Voting Games

Distance-Sensitive Planar Point Location

Fine-Grained Complexity Analysis of Two Classic TSP Variants

Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons

Finding Pairwise Intersections Inside a Query Range

Geodesic Spanners for Points on a Polyhedral Terrain

Fat Polygonal Partitions with Applications to Visualization and Embeddings

Treemaps with Bounded Aspect Ratio

The Traveling Salesman Problem Under Squared Euclidean Distances

See the researcher in context

Building this map preview