### Browsing by Author "de Berg, Mark"

Now showing 1 - 4 of 4

###### Results Per Page

###### Sort Options

Item Clique-Based Separators for Geometric Intersection Graphs(Springer, 2023-06) de Berg, Mark; Kisfaludi-Bak, Sándor; Monemizadeh, Morteza; Theocharous, Leonidas; Department of Computer Science; Professorship Kisfaludi-Bak Sándor; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Eindhoven University of TechnologyLet F be a set of n objects in the plane and let G×(F) be its intersection graph. A balanced clique-based separator of G×(F) is a set S consisting of cliques whose removal partitions G×(F) into components of size at most δn, for some fixed constant δ< 1. The weight of a clique-based separator is defined as ∑ C∈Slog (| C| + 1). Recently De Berg et al. (SIAM J. Comput. 49: 1291-1331. 2020) proved that if S consists of convex fat objects, then G×(F) admits a balanced clique-based separator of weight O(n). We extend this result in several directions, obtaining the following results. (i) Map graphs admit a balanced clique-based separator of weight O(n), which is tight in the worst case. (ii) Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight O(n2 / 3log n). If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to O(nlogn). (iii) Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight O(n2 / 3log n). (iv) Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight O(n+rlog(n/r)), which is tight in the worst case. These results immediately imply sub-exponential algorithms for Maximum Independent Set (and, hence, Vertex Cover), for Feedback Vertex Set, and for q-Coloring for constant q in these graph classes.Item An ETH-Tight Exact Algorithm for Euclidean TSP(Society for Industrial and Applied Mathematics (SIAM), 2023) de Berg, Mark; Bodlaender, Hans L.; Kisfaludi-Bak, Sándor; Kolay, Sudeshna; Eindhoven University of Technology; Utrecht University; Department of Computer Science; Indian Institute of Technology Kharagpur; Department of Computer ScienceWe study exact algorithms for Metric TSP in ℝd. In the early 1990s, algorithms with (Formula Presented) running time were presented for the planar case, and some years later an algorithm with (Formula Presnted) running time was presented for any d\geqslant 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Metric TSP, except for a lower bound stating that the problem admits no (Formula Presented) algorithm unless ETH fails. In this paper we settle the complexity of Metric TSP, up to constant factors in the exponent and under ETH, by giving an algorithm with running time (Formula Presented).Item Euclidean TSP in Narrow Strips(Springer, 2024-06) Alkema, Henk; de Berg, Mark; van der Hofstad, Remco; Kisfaludi-Bak, Sándor; Department of Computer Science; Professorship Kisfaludi-Bak Sándor; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Eindhoven University of TechnologyWe investigate how the complexity of Euclidean TSP for point sets P inside the strip (- ∞, + ∞) × [0 , δ] depends on the strip width δ . We obtain two main results. For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(nlog 2n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ⩽22 , a bound which is best possible.We present an algorithm that is fixed-parameter tractable with respect to δ . Our algorithm has running time 2O(δ)n+O(δ2n2) for sparse point sets, where each 1 × δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0 , n] × [0 , δ] , it has an expected running time of 2O(δ)n . These results generalise to point sets P inside a hypercylinder of width δ . In this case, the factors 2O(δ) become 2O(δ1-1/d) .Item Improved Bounds for Discrete Voronoi Games(Springer, 2023) de Berg, Mark; van Wordragen, Geert; Department of Computer Science; Morin, Pat; Suri, Subhash; Eindhoven University of TechnologyIn the planar one-round discrete Voronoi game, two players P and Q compete over a set V of n voters represented by points in R2. First, P places a set P of k points, then Q places a set Q of ℓ points, and then each voter v∈ V is won by the player who has placed a point closest to v. It is well known that if k= ℓ= 1, then P can always win n/3 voters and that this is worst-case optimal. We study the setting where k> 1 and ℓ= 1. We present lower bounds on the number of voters that P can always win, which improve the existing bounds for all k⩾ 4. As a by-product, we obtain improved bounds on small ε -nets for convex ranges for even numbers of points in general position.