11 papers
A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane
Sarita de Berg, Jacobus Conradi, Peter Kramer +2
The dilation of a geometric graph measures how much longer the path between pairs of points becomes when restricted to graph edges, rather than following the direct path through th…
Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
Sarita de Berg, Nynne Maria Foldager Bække, Frida Astrup Eriksen +3
In the imprecise geometry model, the input is an imprecise point set, which is a family of regions , where for each one may retrieve the true point $p_…
A dynamic -spanner for disk intersection graphs
Sarita de Berg, Ivor van der Hoog, Eva Rotenberg +2
We maintain a -spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in for some fixed and known…
The Contiguous Art Gallery Problem is in Θ(n log n)
Sarita de Berg, Jacobus Conradi, Ivor van der Hoog +1
Recently, a natural variant of the Art Gallery problem, known as the \emph{Contiguous Art Gallery problem} was proposed. Given a simple polygon , the goal is to partition its bo…
The Complexity of Geodesic Spanners using Steiner Points
Sarita de Berg, Tim Ophelders, Irene Parada +2
A geometric -spanner on a set of point sites in a metric space is a subgraph of the complete graph on such that for every pair of sites the d…
Exact solutions to the Weighted Region Problem
Sarita de Berg, Guillermo Esteban, Rodrigo I. Silveira +1
In this paper, we consider the Weighted Region Problem. In the Weighted Region Problem, the length of a path is defined as the sum of the weights of the subpaths within each region…
Competitive Searching over Terrains
Sarita de Berg, Nathan van Beusekom, Max van Mulken +2
We study a variant of the searching problem where the environment consists of a known terrain and the goal is to obtain visibility of an unknown target point on the surface of the…
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…
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…
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…
Dynamic Data Structures for -Nearest Neighbor Queries
Sarita de Berg, Frank Staals
Our aim is to develop dynamic data structures that support -nearest neighbors (-NN) queries for a set of point sites in the plane in time, where is s…