1 citations · 2 across the 20 of their papers we have counts for
27 papers
Adaptive Sorting, also in the BST Model
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Sorting is one of the most basic algorithmic problems. Adaptive sorting algorithms exploit features that make an input easier to sort, often captured by entropy measures. Many such…
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_…
Tight Fréchet bounds for -low density curves
Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl +1
The Fréchet distance is a well-studied similarity measure between curves. We computing the Fréchet distance between -low-density curves, the most general of realistic curve assu…
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…
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_…
Engineering Fully Dynamic Convex Hulls
Ivor van der Hoog, Henrik Reinstädtler, Eva Rotenberg
We present a new fully dynamic algorithm for maintaining convex hulls under insertions and deletions while supporting geometric queries. Our approach combines the logarithmic metho…
The Presort Hierarchy for Geometric Problems
Ivor van der Hoog, Eva Rotenberg, Jack Spalding-Jamieson +1
Many fundamental problems in computational geometry admit no algorithm running in time for planar input points, via classical reductions from sorting. Prominent e…
On computing the (exact) Fréchet distance with a frog
Jacobus Conradi, Ivor van der Hoog, Eva Rotenberg
The continuous Frechet distance between two polygonal curves is classically computed by exploring their free space diagram. Recently, Har-Peled, Raichel, and Robson [SoCG'25] propo…
Tight Adaptive Bounds for Convex Hulls
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Adaptive sorting algorithms exploit existing order in the input to obtain better-than-worst-case running times. A classical example is sorting by runs: if the input can be partitio…
The Complexity of Stackelberg Pricing Games
Christoph Grüne, Dorothee Henke, Eva Rotenberg +1
We consider Stackelberg pricing games, which are also known as bilevel pricing problems, or combinatorial price-setting problems. This family of problems consists of games between…
Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
The element distinctness problem takes as input a list of values from a totally ordered universe and the goal is to decide whether contains any duplicates. It is a well…
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…
Practical Insertion-Only Convex Hull
Ivor van der Hoog, Henrik Reinstädtler, Eva Rotenberg
Convex hull data structures are fundamental in computational geometry. We study insertion-only data structures, supporting various containment and intersection queries. When is…
Simpler is Faster: Practical Distance Reporting by Sorting Along a Space-Filling Curve
Sarita de Berg, Emil Toftegaard Gæde, Ivor van der Hoog +2
Range reporting is a classical problem in computational geometry. A (rectangular) reporting data structure stores a point set , such that, given a (rectangular) query region …
A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
For a planar point set , its convex hull is the smallest convex polygon that encloses all points in . The construction of the convex hull from an array containing i…
Fréchet Distance in Unweighted Planar Graphs
Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg +1
The Fréchet distance is a distance measure between trajectories in or walks in a graph . Given constant-time shortest path queries, the Discrete Fréchet distance $D_…
Simpler Universally Optimal Dijkstra
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Let G be a weighted (directed) graph with n vertices and m edges. Given a source vertex s, Dijkstra's algorithm computes the shortest path lengths from s to all other vertices in O…
Instance-Optimal Imprecise Convex Hull
Sarita de Berg, Ivor van der Hoog, Eva Rotenberg +2
Imprecise measurements of a point set P = (p1, ..., pn) can be modelled by a family of regions F = (R1, ..., Rn), where each imprecise region Ri contains a unique point pi. A retri…
Efficient Greedy Discrete Subtrajectory Clustering
Ivor van der Hoog, Lara Ost, Eva Rotenberg +1
We cluster a set of trajectories T using subtrajectories of T. Clustering quality may be measured by the number of clusters, the number of vertices of T that are absent from the cl…
Dynamic Indexing Through Learned Indices with Worst-case Guarantees
Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg +1
Indexing data is a fundamental problem in computer science. Recently, various papers apply machine learning to this problem. For a fixed integer , a \emph{learned inde…
Local Density and its Distributed Approximation
Aleksander Bjørn Christiansen, Ivor van der Hoog, Eva Rotenberg
The densest subgraph problem is a classic problem in combinatorial optimisation. Danisch, Chan, and Sozio propose a definition for \emph{local density} that assigns to each vertex…
Simpler Optimal Sorting from a Directed Acyclic Graph
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Fredman proposed in 1976 the following algorithmic problem: Given are a ground set , some partial order over , and some comparison oracle that specifies a linear or…
Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs
Ivor van der Hoog, André Nusser, Eva Rotenberg +1
A classical problem in computational geometry and graph algorithms is: given a dynamic set S of geometric shapes in the plane, efficiently maintain the connectivity of the intersec…