2 citations · 3 across the 10 of their papers we have counts for
11 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…
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…
Soft Sequence Heaps
Gerth Stølting Brodal
Chazelle [JACM00] introduced the soft heap as a building block for efficient minimum spanning tree algorithms, and recently Kaplan et al. [SOSA2019] showed how soft heaps can be ap…
Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees
Gerth Stølting Brodal, Konstantinos Mampentzidis
We study the problem of computing the triplet distance between two rooted unordered trees with labeled leafs. Introduced by Dobson 1975, the triplet distance is the number of l…
Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time
Gerth Stølting Brodal, Jesper Sindahl Nielsen, Jakob Truelsen
The binary heap of Williams (1964) is a simple priority queue characterized by only storing an array containing the elements and the number of elements - here denoted a strictl…
Optimal Planar Orthogonal Skyline Counting Queries
Gerth Stølting Brodal, Kasper Green Larsen
The skyline of a set of points in the plane is the subset of maximal points, where a point is maximal if no other point satisfies and . We cons…
Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time
Gerth Stølting Brodal, Alexis C. Kaporis, Apostolos N. Papadopoulos +3
This work studies the problem of 2-dimensional searching for the 3-sided range query of the form in both main and external memory, by considering a vari…
Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property
Gerth Stølting Brodal, Casper Kejlberg-Rasmussen
In this paper we present an implicit dynamic dictionary with the working-set property, supporting insert(e) and delete(e) in O(log n) time, predecessor(e) in O(log l_{p(e)}) time,…