20 citations · 23 across the 21 of their papers we have counts for
24 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…
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_…
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 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…
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…
Tight Bounds for Sorting Under Partial Information
Ivor van der Hoog, Daniel Rutschmann
Sorting has a natural generalization where the input consists of: (1) a ground set of size , (2) a partial oracle specifying some fixed partial order on and (3…
Barking dogs: A Fréchet distance variant for detour detection
Ivor van der Hoog, Fabian Klute, Irene Parada +1
Imagine you are a dog behind a fence and a hiker is passing by at constant speed along the hiking path . In order to fulfil your duties as a watchdog, you desire to bark as…
Faster, Deterministic and Space Efficient Subtrajectory Clustering
Ivor van der Hoog, Thijs van der Horst, Tim Ophelders
Given a trajectory and a distance , we wish to find a set of curves of complexity at most , such that we can cover with subcurves that each are within Fréchet…
Dynamic Dynamic Time Warping
Karl Bringmann, Nick Fischer, Ivor van der Hoog +3
The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, espe…
Adaptive Out-Orientations with Applications
Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm +4
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…
Simple and Robust Dynamic Two-Dimensional Convex Hull
Emil Toftegaard Gæde, Inge Li Gørtz, Ivor van der Hoog +2
The convex hull of a data set is the smallest convex set that contains . In this work, we present a new data structure for convex hull, that allows for efficient dynamic upd…
Data Structures for Approximate Discrete Fréchet Distance
Ivor van der Hoog, Eva Rotenberg, Sampson Wong
The Fréchet distance is a popular distance measure between curves and . Conditional lower bounds prohibit -approximate Fréchet distance computations in st…
Adaptive Out-Orientations with Applications
Aleksander B. G. Christiansen, Jacob Holm, Ivor van der Hoog +2
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…
On the Discrete Fréchet Distance in a Graph
Anne Driemel, Ivor van der Hoog, Eva Rotenberg
The Fréchet distance is a well-studied similarity measure between curves that is widely used throughout computer science. Motivated by applications where curves stem from paths and…
Smoothing the gap between NP and ER
Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER). A problem is ER-complete if it is as hard as the problem ETR and if i…
Topological Stability of Kinetic -Centers
Ivor van der Hoog, Marc van Kreveld, Wouter Meulemans +2
We study the -center problem in a kinetic setting: given a set of continuously moving points in the plane, determine a set of (moving) disks that cover at every time…
Dynamic smooth compressed quadtrees (Fullversion)
Ivor Hoog v. d., Elena Khramtcova, Maarten Löffler
We introduce dynamic smooth (a.k.a. balanced) compressed quadtrees with worst-case constant time updates in constant dimensions. We distinguish two versions of the problem. First,…
Maximum-Area Triangle in a Convex Polygon, Revisited
Vahideh Keikha, Maarten Löffler, Ali Mohades +2
We revisit the following problem: Given a convex polygon , find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobki…