Mark de Berg

Peyman Afshani, Mark de Berg, Kevin Buchin et al.

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.

Mark de Berg, Prosenjit Bose, Leonidas Theocharous

Many algorithmic problems can be solved (almost) as efficiently in metric spaces of bounded doubling dimension as in Euclidean space. Unfortunately, the metric space defined by points in a simple polygon equipped with the geodesic distance does not necessarily have bounded doubling dimension. We therefore study the doubling dimension of fat polygons, for two well-known fatness definitions. We prove that locally-fat simple polygons do not always have bounded doubling dimension, while any $(α,β)$-covered polygon does have bounded doubling dimension (even if it has holes). We also study the perimeter of geodesically convex sets in $(α,β)$-covered polygons (possibly with holes), and show that this perimeter is at most a constant times the Euclidean diameter of the set. Using these two results, we obtain new results for several problems on $(α,β)$-covered polygons, including an algorithm that computes the closest pair of a set of $m$ points in an $(α,β)$-covered polygon with $n$ vertices that runs in $O(n + m\log{n})$ expected time.

Mark de Berg, Bart M. P. Jansen, Jeroen S. K. Lamme

We study SINGLE-SOURCE SHORTEST PATH (SSSP) on unweighted intersection graphs whose node set corresponds to a set of $n$ constant-complexity objects in the plane. We prove SSSP can be solved in $O(U(n)\ \mathrm{polylog}\,n)$ expected time for any class of objects whose union complexity is $U(n)$. In particular, we obtain an $O(n 2^{α(n)}\log^2 n)$ algorithm for arbitrary pseudodisks, and an $O(λ_{s+2}(n)2^{O(\log^* n)} \log^2 n)$ algorithm for locally fat objects. This significantly extends the class of objects for which SSSP can be solved in $O(n\ \mathrm{polylog}\, n)$ time: so far, $O(n\ \mathrm{polylog}\, n)$ SSSP algorithms were not even known for pseudodisks that are fat and convex and similarly-sized. Our second result concerns the DIAMETER problem, which asks for the maximum distance between any two nodes in a graph. Even for intersection graphs, near-quadratic algorithms are difficult to obtain, and the $O(n^2\ \mathrm{polylog}\, n)$ running time that follows from our SSSP algorithm is the first near-quadratic running time for such general classes of intersection graphs. Obtaining subquadratic running time is even more challenging. We prove that the diameter of a set of arbitrary pseudodisks can be computed almost exactly, namely up to an additive error of 2, in $\tilde{O}(n^{2-1/14})$ expected time. This generalizes and speeds up a recent algorithm by Chang, Gao, and Le~(SoCG 2024) that works for similarly-sized disks (or similarly-sized pseudodisks that are fat and satisfy a strong monotonicity assumption) and runs in $\tilde{O}(n^{2-1/18})$ time. To this end, we develop a so-called star-based $r$-clustering for intersection graphs of pseudodisks, which is interesting in its own right. Our star-based $r$-clustering can also be used to obtain an almost exact distance oracle for pseudodisks that uses $O(n^{2-1/13})$ storage and has $O(1)$ query time.

Peyman Afshani, Mark De Berg, Kevin Buchin et al.

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.

Aviv Adler, Mark de Berg, Dan Halperin et al.

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.