4 papers
Partition-based Simple Heaps
Gerth Stølting Brodal, John Iacono, Casper Moldrup Rysgaard +1
We introduce a new family of priority-queue data structures: partition-based simple heaps. The structures consist of doubly-linked lists; order is enforced among data i…
Towards Lazy B-Trees
Casper Moldrup Rysgaard, Sebastian Wild
Lazy search trees (Sandlund & Wild FOCS 2020, Sandlund & Zhang SODA 2022) are sorted dictionaries whose update and query performance smoothly interpolates between that of efficient…
The Contiguous Art Gallery Problem is Solvable in Polynomial Time
Magnus Christian Ring Merrild, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou +1
In this paper, we study the Contiguous Art Gallery Problem, introduced by Thomas C. Shermer at the 2024 Canadian Conference on Computational Geometry, a variant of the classical ar…
Buffered Partially-Persistent External-Memory Search Trees
Gerth Stølting Brodal, Casper Moldrup Rysgaard, Rolf Svenning
We present an optimal partially-persistent external-memory search tree with amortized I/O bounds matching those achieved by the non-persistent -tree by Brodal and…