21 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_…
HRsR: Hierarchical Rotation System Reconstruction
Ruiqi Cui, Cem AkarsubaÅı, Emil Toftegaard Gæde +3
Surface reconstruction from point clouds remains challenging when both geometric fidelity and topology control are required. Rotation System Reconstruction (RsR) reconstructs trian…
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_…
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…