Ivor van der Hoog

Sarita de Berg, Jacobus Conradi, Ivor van der Hoog et al.

Recently, a natural variant of the Art Gallery problem, known as the \emph{Contiguous Art Gallery problem} was proposed. Given a simple polygon $P$, the goal is to partition its boundary $\partial P$ into the smallest number of contiguous segments such that each segment is completely visible from some point in $P$. Unlike the classical Art Gallery problem, which is NP-hard, this variant is polynomial-time solvable. At SoCG~2025, three independent works presented algorithms for this problem, each achieving a running time of $O(k n^5 \log n)$ (or $O(n^6\log n)$), where $k$ is the size of an optimal solution. Interestingly, these results were obtained using entirely different approaches, yet all led to roughly the same asymptotic complexity, suggesting that such a running time might be inherent to the problem. We show that this is not the case. In the real RAM-model, the prevalent model in computational geometry, we present an $O(n \log n)$-time algorithm, achieving an $O(k n^4)$ factor speed-up over the previous state-of-the-art. We also give a straightforward sorting-based lower bound by reducing from the set intersection problem. We thus show that the Contiguous Art Gallery problem is in $Θ(n \log n)$.

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(m + n log n) time. This bound is known to be worst-case optimal via a reduction to sorting. Theoretical computer science has developed numerous fine-grained frameworks for analyzing algorithmic performance beyond standard worst-case analysis, such as instance optimality and output sensitivity. Haeupler et al. [FOCS '24] consider the notion of universal optimality, a refined complexity measure that accounts for both the graph topology and the edge weights. For a fixed graph topology, the universal running time of a weighted graph algorithm is defined as its worst-case running time over all possible edge weightings of G. An algorithm is universally optimal if no other algorithm achieves a better asymptotic universal running time on any particular graph topology. They show that Dijkstra's algorithm can be made universally optimal by replacing the heap with a custom data structure. We revisit their result. We introduce a simple heap property called timestamp optimality, where the cost of popping an element x is logarithmic in the number of elements inserted between pushing and popping x. We show that timestamp optimal heaps are not only easier to define but also easier to implement. Using these timestamps, we provide a significantly simpler proof that Dijkstra's algorithm, with the right kind of heap, is universally optimal.

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 method with a deletion-only convex hull data structure, achieving amortised update times of $O(\log n \log \log n)$ and query times of $O(\log^2 n)$. We provide a robust and non-trivial implementation that supports point-location queries, a challenging and non-decomposable class of convex hull queries. We evaluate our implementation against the state of the art, including a new naive baseline that rebuilds the convex hull whenever an update affects it. On hulls that include polynomially many data points (e.g. $Θ(n^\varepsilon)$ for some $\varepsilon$), such as the ones that often occur in practice, our method outperforms all other techniques. Update-heavy workloads strongly favour our approach, which is in line with our theoretical guarantees. Yet, our method remains competitive all the way down to when the update to query ratio is $1$ to $10$. Experiments on real-world data sets furthermore reveal that existing fully dynamic techniques suffer from significant robustness issues. In contrast, our implementation remains stable across all tested inputs.

Sarita de Berg, Ivor van der Hoog, Eva Rotenberg et al.

We maintain a $(1+\varepsilon)$-spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in $[4,Ψ]$ for some fixed and known $Ψ$. The resulting $(1+\varepsilon)$-spanner has size $O(n \varepsilon^{-2} \log Ψ\log (\varepsilon^{-1}))$, where $n$ is the present number of disks. We develop a novel use of persistent data structures to dynamically maintain our $(1+\varepsilon)$-spanner. Our approach requires $O(\varepsilon^{-2} n \log^4 n \log Ψ)$ space and has an $O( \left( \fracΨ{\varepsilon} \right)^2 \log^4 n \log^2 Ψ\log^2 (\varepsilon^{-1}))$ expected amortised update time. For constant $\varepsilon$ and $Ψ$, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time. Furthermore, we observe that for any $\varepsilon < 1$, our spanner also serves as a connectivity data structure. With a slight adaptation of our techniques, this leads to better bounds for dynamically supporting connectivity queries in a disk intersection graph. In particular, we improve the space usage when compared to the dynamic data structure of (Baumann et al., DCG'24), replacing the linear dependency on $Ψ$ by a polylogarithmic dependency. Finally, we generalise our results to $d$-dimensional hypercubes.

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] proposed a radically different approach: instead of directly traversing the continuous free space, they approximate the distance by computing paths in a discrete graph derived from the discrete free space, recursively bisecting edges until the discrete distance converges to the continuous Frechet distance. They implement this so-called frog-based technique and report substantial practical speedups over the state of the art. We revisit the frog-based approach and address three of its limitations. First, the method does not compute the Frechet distance exactly. Second, the recursive bisection procedure only introduces the monotonicity events required to realise the Frechet distance asymptotically, that is, only in the limit. Third, the applied simplification technique is heuristic. Motivated by theoretical considerations, we develop new techniques that guarantee exactness, polynomial-time convergence, and near-optimal lossless simplifications. We provide an open-source C++ implementation of our variant. Our primary contribution is an extensive empirical evaluation. As expected, exact computation introduces overhead and increases the median running time. Yet, our method is often faster in the worst case, the slowest ten percent of instances, or even on average due to its convergence guarantees. More surprisingly, in our experiments, the implementation of Bringmann, Kuennemann, and Nusser [SoCG'19] consistently outperforms all frog-based approaches in practice. This appears to contrast published claims of the efficiency of the frog-based techniques. These results thereby provide nuanced perspective on frogs: highlighting both the theoretical appeal, but also the practical limitations.

Sarita de Berg, Nynne Maria Foldager Bække, Frida Astrup Eriksen et al.

In the imprecise geometry model, the input is an imprecise point set, which is a family of regions $F = (R_1, \ldots,R_n)$, where for each $R_i$ one may retrieve the true point $p_i \in R_i$. By preprocessing $F$, we can construct the output, in our case the Pareto front, on $P$ faster. We efficiently construct the Pareto front of an imprecise point set in the plane. Efficiency is interpreted in two ways: minimizing (i) the number of retrievals, and (ii) the computation time used to determine the set of regions that must be retrieved and to construct the Pareto front. We present an algorithm to construct the Pareto front for possibly overlapping rectangles that is \emph{instance-optimal} with respect to the number of retrievals, meaning that for every fixed input $(F, P)$, there is no algorithm that retrieves asymptotically fewer regions to compute the output. This is a strong algorithmic quality, as it means that our algorithm is competitive even to clairvoyant algorithms which know a correct guess of the output and only have to verify its correctness. In terms of algorithmic running time, instance-optimality is provably unobtainable. We instead present an algorithm which is within a $\log n$-factor of instance-optimality. This generalizes earlier results to overlapping input regions, at only a minor cost in running time. For unit squares, we present an algorithm that is not only instance-optimal in the number of retrievals, but also \emph{universally} optimal in terms of running time, meaning that for any fixed set of regions $F$, no algorithm has a better worst-case running time for all possible point sets $P$. This is the first universally optimal algorithm for overlapping planar input. Compared to previous work, this result improves the degree of overlap, the preprocessing time, the number of retrievals, and the running time.

Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan et al.

Computing the convex hull of a planar $n$-point set $P$ is one of the most fundamental problems in computational geometry. It has an $Ω(n \log n)$ lower bound in the algebraic computation tree model, and many convex hull algorithms match this bound. Classical results show that, under special input assumptions, sub-$O(n \log n)$ algorithms are possible. For instance, when the points are given in lexicographic or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist. This naturally raises the question: can the convex hull of a point set be computed in sub-$O(n \log n)$ time under weaker input assumptions? We answer this positively. Under the promise that the input sequence contains the convex hull as a subsequence, we give a deterministic $O(n \sqrt{\log n})$-time algorithm to compute the convex hull of $P$. With randomisation, we achieve expected running time $O(n \log^{\varepsilon} n)$ for any constant $\varepsilon > 0$. We find this surprising, as points not on the convex hull may behave adversarially toward our convex hull construction algorithm. Yet the promise that \emph{only} the hull points are sorted suffices for $o(n \log n)$-time algorithms. Finally, we show that this promise is tight: if it is even slightly broken, i.e., allowing just one hull point to appear out of order, we prove an adversarial $Ω(n \log n)$-time lower bound. Consequently, the promise cannot be verified with fewer than $Ω(n \log n)$ comparisons. This also negatively resolves an open problem of Löffler and Raichel, who conjectured sub-$O(n \log n)$-time algorithms for computing the convex hull of a supersequence containing the hull as a subsequence.

Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl et al.

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 the $d$-dimensional grid graphs, i.e. $\mathbb{Z}^d$ where points share an edge if they differ by one in one coordinate. We give an algorithm, that for two simple paths on $n$ vertices, $(1+\varepsilon)$-approximates the Fréchet distance in time $\widetilde{O}((\frac{n}{\varepsilon})^{2-2/d} +n)$. We complement this by a near-matching fine-grained lower bound: for constant dimensions $d \geq 3$, there is no $O((\varepsilon^{2/d}(\frac{n}{\varepsilon})^{2-2/d})^{1-δ})$ algorithm for any $δ>0$ unless the Orthogonal Vector Hypothesis fails. Thus, our results are tight up to a factor $\varepsilon^{2/d}$ and $\log(n)$-factors. We extend our results to imbalanced lower and upper bounds, where the curves have $n$ and $m$ vertices respectively, and also obtain near-tight bounds. Driemel, Har-Peled and Wenk [DCG'12] studied \emph{realistic assumptions} for curves to speed up Fréchet distance computation. One of these assumptions is $λ$-low density and they can compute a $(1+\varepsilon)$-approximation between $λ$-low dense curves in time $\widetilde{O}( \varepsilon^{-2} λ^2 n^{2(1-1/d)})$. By adapting our lower bound, we show that their algorithm has a tight dependency on $n$ and a tight dependency on $\varepsilon$ as $d$ goes to infinity. A gap remains in terms of $λ$.

Ivor van der Hoog, John Iacono, Eva Rotenberg et al.

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($x_i$) pushes a new value $x_i$ onto the heap, and DecreaseKey($i$, $v$) decreases the value $x_i$ to $v$. A working-set heap is a heap that supports the $x_i \gets$ pop$()$ operation in $O(\log Γ(x_i) )$ time where $Γ(x_i)$ is the size of the \emph{working set}: the number of elements that were pushed onto the heap while $x_i$ was in the heap. The goal of working set heap design is to maintain the working set property while minimizing the overhead of the Push and DecreaseKey operations. On a word RAM, there exist working set heaps that support Push and DecreaseKey in amortized constant time. In this paper, we show via a simple construction that pointer machines, one of the most general and least-assuming computational models, support working set heaps that support Push in amortized constant time and DecreaseKey in inverse-Ackermann time. A by-product of this analysis is that Dijkstra's shortest path algorithm can be near-universally optimal on a pointer machine -- incurring only an additive $O(m \, α(m))$ overhead compared to the optimal running time for distance ordering, where $m$ denotes the number of edges in the graph.

Ivor van der Hoog, Eva Rotenberg, Jack Spalding-Jamieson et al.

Many fundamental problems in computational geometry admit no algorithm running in $o(n \log n)$ time for $n$ planar input points, via classical reductions from sorting. Prominent examples include the computation of convex hulls, quadtrees, onion layer decompositions, Euclidean minimum spanning trees, KD-trees, Voronoi diagrams, and decremental closest-pair. A classical result shows that, given $n$ points sorted along a single direction, the convex hull can be constructed in linear time. Subsequent works established that for all of the other above problems, this information does not suffice. In 1989, Aggarwal, Guibas, Saxe, and Shor asked: Under which conditions can a Voronoi diagram be computed in $o(n \log n)$ time? Since then, the question of whether sorting along TWO directions enables a $o(n \log n)$-time algorithm for such problems has remained open and has been repeatedly mentioned in the literature. In this paper, we introduce the Presort Hierarchy: A problem is 1-Presortable if, given a sorting along one axis, it permits a (possibly randomised) $o(n \log n)$-time algorithm. It is 2-Presortable if sortings along both axes suffice. It is Presort-Hard otherwise. Our main result is that quadtrees, and by extension Delaunay triangulations, Voronoi diagrams, and Euclidean minimum spanning trees, are 2-Presortable: we present an algorithm with expected running time $O(n \sqrt{\log n})$. This addresses the longstanding open problem posed by Aggarwal, Guibas, Saxe, and Shor (albeit randomised). We complement this result by showing that some of the other above geometric problems are also 2-Presortable or Presort-Hard.