4 papers · 1 filter
The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
Peyman Afshani, Gerth Stølting Brodal, Nodari Sitchinava
We prove that no deterministic output-sensitive algorithm for the planar convex hull and maxima problems can obtain both optimal time and I/O complexity, where the optimality is de…
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…
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…
Bottom-up Rebalancing Binary Search Trees by Flipping a Coin
Gerth Stølting Brodal
Rebalancing schemes for dynamic binary search trees are numerous in the literature, where the goal is to maintain trees of low height, either in the worst-case or expected sense. I…