4 papers
Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
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 constant-complexity objects in the plane. We prove SSSP can…
On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons
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 poi…
Star-Based Separators for Intersection Graphs of -Colored Pseudo-Segments
M. de Berg, B. M. P. Jansen, J. S. K. Lamme
The Planar Separator Theorem, which states that any planar graph has a separator consisting of nodes whose removal partitions into compone…
On Stable Approximation Algorithms for Geometric Coverage Problems
Mark de Berg, Arpan Sadhukhan
Let be a set of points in the plane and let be an integer. The goal of Max Cover by Unit Disks problem is to place unit disks whose union covers the maximum number of p…