Showing 2023Show all
3 papers · 1 filter
cs.CG2023
Clustering with Few Disks to Minimize the Sum of Radii
Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer +2
Given a set of points in the Euclidean plane, the -MinSumRadius problem asks to cover this point set using disks with the objective of minimizing the sum of the radii of…
cs.CG2023
The Complexity of Geodesic Spanners
Sarita de Berg, Marc van Kreveld, Frank Staals
A geometric -spanner for a set of point sites is an edge-weighted graph for which the (weighted) distance between any two sites is at most times the orig…
cs.CG2023
Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
Sarita de Berg, Tillmann Miltzow, Frank Staals
We devise a data structure that can answer shortest path queries for two query points in a polygonal domain on vertices. For any , the space complexity of…