Arrow Research search

Author name cluster

Mark de Berg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

TCS Journal 2019 Journal Article

The complexity of Dominating Set in geometric intersection graphs

  • Mark de Berg
  • Sándor Kisfaludi-Bak
  • Gerhard Woeginger

We study the parameterized complexity of the dominating set problem in geometric intersection graphs. • In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP -complete and contained in FPT (when parameterized by the solution size). • In two and higher dimensions, we prove that Dominating Set is contained in W [ 1 ] for intersection graphs of semi-algebraic sets with constant description complexity. So far this was only known for unit squares. Finally, we establish W [ 1 ] -hardness for a large class of intersection graphs.

Details DOI

FOCS Conference 2018 Conference Paper

An ETH-Tight Exact Algorithm for Euclidean TSP

  • Mark de Berg
  • Hans L. Bodlaender
  • Sándor Kisfaludi-Bak
  • Sudeshna Kolay

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 later an algorithm with n O(n1-1/d) running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2 O (n 1-1/d-ε ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2 O(n1-1/d) algorithm and by showing that a 2 o(n1-1/d) algorithm does not exist unless ETH fails.

Details

SODA Conference 2017 Conference Paper

Geodesic Spanners for Points on a Polyhedral Terrain

  • Mohammad Ali Abam
  • Mark de Berg
  • Mohammad Javad Rezaei Seraji

Let S be a set S of n points on a polyhedral terrain T in ℝ 3, and let ∊ > 0 be a fixed constant. We prove that S admits a (2 + ∊)-spanner with O ( n log n ) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in ℝ d admits an additively weighted (2 + ∊)-spanner with O ( n ) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ∊), and almost matches the lower bound.

Details

FOCS Conference 2017 Conference Paper

Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments

  • Mark de Berg

More than 25 years ago, inspired by applications in computer graphics, Chazelle et al. (FOCS 1991) studied the following question: Is it possible to cut any set of n lines or other objects in R 3 into a subquadratic number of fragments such that the resulting fragments admit a depth order? They managed to prove an O(n 9/4 ) bound on the number of fragments, but only for the very special case of bipartite weavings of lines. Since then only little progress was made, until a recent breakthrough by Aronov and Sharir (STOC 2016) who showed that O(n 3/2 polylog n) fragments suffice for any set of lines. In a follow-up paper Aronov, Miller and Sharir (SODA 2017) proved an O(n 3/2+ε ) bound for triangles, but their method uses high-degree algebraic arcs to perform the cuts. Hence, the resulting pieces have curved boundaries. Moreover, their method uses polynomial partitions, for which currently no algorithm is known. Thus the most natural version of the problem is still wide open: Is it possible to cut any collection of n disjoint triangles in R3 into a subquadratic number of triangular fragments that admit a depth order? And if so, can we compute the cuts efficiently? We answer this question by presenting an algorithm that cuts any set of n disjoint triangles in R3 into O(n 7/4 polylog n) triangular fragments that admit a depth order. The running time of our algorithm is O(n 3. 69 ). We also prove a refined bound that depends on the number, K, of intersections between the projections of the triangle edges onto the xy-plane: we show that O(n 1+ε + n 1/4 K 3/4 polylog n) fragments suffice to obtain a depth order. This result extends to xy-monotone surface patches bounded by a constant number of bounded-degree algebraic arcs in general position, constituting the first subquadratic bound for surface patches. Finally, as a byproduct of our approach we obtain a faster algorithm to cut a set of lines into O(n 3/2 polylog n) fragments that admit a depth order. Our algorithm for lines runs in O(n 5. 38 ) time, while the previous algorithm uses O(n 8. 77 ) time.

Details

ICRA Conference 2010 Conference Paper

Computing push plans for disk-shaped robots

  • Mark de Berg
  • Dirk H. P. Gerrits

Suppose we want to move a passive object along a given path, among obstacles in the plane, by pushing it with an active robot. We present two algorithms to compute a push plan for the case that the object and robot are disks and the obstacles are non-intersecting line segments. The first algorithm assumes that the robot must maintain contact with the object at all times, and produces a shortest path. There are also situations, however, where the robot has no choice but to let go of the object occasionally. Our second algorithm handles such cases, but no longer guarantees that the produced path is the shortest possible.

Details

TCS Journal 1995 Journal Article

Reaching a goal with directional uncertainty

  • Mark de Berg
  • Leonidas Guibas
  • Dan Halperin
  • Mark Overmars
  • Otfried Schwarzkopf
  • Micha Sharir
  • Monique Teillaud

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region R α(S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of R α(S) is O( n α5 ). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k 3 m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

Details DOI

FOCS Conference 1990 Conference Paper

Hidden Surface Removal for Axis-Parallel Polyhedra (Extended Abstract)

  • Mark de Berg
  • Mark H. Overmars

An efficient, output-sensitive method for computing the visibility map of a set of axis-parallel polyhedra (i. e. polyhedra with their faces and edges parallel to the coordinate axes) as seen from a given viewpoint is introduced. For nonintersecting polyhedra with n edges in total, the algorithm runs in time O((n+k)log n), where k is the complexity of the visibility map. The method can handle cyclic overlap of the polyhedra and perspective views without any problem. For c-oriented polyhedra (with faces and edges in c orientations, for some constant c) the method can be extended to run in the same time bound. The method can be extended even further to deal with intersecting polyhedra with only a slight increase in the time bound. >

Details