2 citations · 3 across the 10 of their papers we have counts for
14 papers
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…
Dynamic Convex Hulls for Simple Paths
Bruce Brewer, Gerth Stølting Brodal, Haitao Wang
We consider the planar dynamic convex hull problem. In the literature, solutions exist supporting the insertion and deletion of points in poly-logarithmic time and various queries…
Deterministic Cache-Oblivious Funnelselect
Gerth Stølting Brodal, Sebastian Wild
In the multiple-selection problem one is given an unsorted array of elements and an array of query ranks , and the task is to return, in sorted order, t…