Showing 2026Show all
2 papers · 1 filter
cs.CG2026
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…
cs.CG2026
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…