23 papers
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 know…
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…
Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines
Ivor van der Hoog, John Iacono, Eva Rotenberg +1
A heap is a dynamic data structure that stores a set of labeled values under the following operations: pop returns the minimum value of the heap, Push() pushes a new value $x_…
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_…
Computing Planar Convex Hulls with a Promise
Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan +5
Computing the convex hull of a planar -point set is one of the most fundamental problems in computational geometry. It has an lower bound in the algebraic com…
Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl +1
The Fréchet distance is a popular distance measure between trajectories or curves in space, or between walks in graphs. We study computing the Fréchet distance between walks in t…