Eva Rotenberg

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, 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.

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)$.

Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg et al.

We consider the following game played in the Euclidean plane: There is any countable set of unit speed lions and one fast man who can run with speed $1+\varepsilon$ for some value $\varepsilon>0$. Can the man survive? We answer the question in the affirmative for any $\varepsilon>0$.